№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Hi there!

In this blog I would like to share some of the code snippets that can shorten your time in future contests. Of course, I'll ignore the "international snippets"

like:

#define SZ(a) (ll)a.size()
#define FOR(i,a,b) for (ll i=(ll)a; i<=(ll)b; i++)
#define f first
#define mp make_pair
#define s second
#define p pair
#define all(C) C.begin(), C.end()

Sometimes you may find typing the identical thing again and again is boring, this blog is about some method that a few people use to get rid of them (or just only me).

So, let's get started.

Scanning/printing the whole vector in a single `std::cin/std::cout`

Snippet

template<typename T> istream& operator>>(istream& in, vector<T>& a) {for(auto &x : a) in >> x; return in;};
template<typename T> ostream& operator<<(ostream& out, vector<T>& a) {for(auto &x : a) out << x << ' '; return out;};

Usage

vector<int> a(10);
cin >> a;
cout << a << endl;

10 is just a random number. It works for any size of the vector.

Scanning/printing `std::pair`

Snippet

template<typename T1, typename T2> ostream& operator<<(ostream& out, const p<T1, T2>& x) {return out << x.f << ' ' << x.s;}
template<typename T1, typename T2> istream& operator>>(istream& in, p<T1, T2>& x) {return in >> x.f >> x.s;}

Usage

pair<int, int> a;
cin >> a;
cout << a;

Ordered set and ordered multiset

Snippet

template<typename T> using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template<typename T> using ordered_multiset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

Usage

ordered_set<int> OS;
ordered_multiset<int> OMS;

Short declaration of 2D and 3D vectors

Snippet

template<typename T> using matrix = vector<vector<T> >;
template<typename T> using rubik = vector<vector<vector<T> > >;

Usage

rubik<int> a; // instead of vector<vector<vector<int> > > a;

Erase repeated neighbor elements

Snippet

template<typename T> void Unique(T &a) {a.erase(unique(a.begin(), a.end()), a.end());}

Usage

vector<int> a;
Unique(a);

Prime test for large numbers

Snippet

ll powermod(ll a, ll b, ll m)
{
	if (b == 0) return 1;
	ull k = powermod(a, b / 2, m);
	k = k * k;
	k %= m;
	if (b & 1) k = (k * a) % m;
	return k;
}

// Prime test for large numbers

bool isPrime(ull n, int iter = 5) 
{
    if (n < 4) return n == 2 || n == 3;
	if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 0; i < iter; i++) 
	{
        ull a = 2 + rand() % (n - 3);
        if (powermod(a, n - 1, n) != 1) return false;
    }
    return true;
}

Longest Increasing Subsequence

Snippet

multiset<ll> LIS(vector<ll> A)
{
	ll a = A.size();
	multiset<ll> S;
	multiset<ll>::iterator it;
	FOR(i, 0, a - 1)
	{
		S.insert(A[i]);
		it = S.upper_bound(A[i]);
		if (it != S.end()) S.erase(it);
	}
	return S;
}

Longest Strictly Increasing Subsequence

Snippet

multiset<ll> LSIS(vector<ll> A) // a.k.a Longest Strictly Increasing Sequence
{
	ll a = A.size();
	multiset<ll> S;
	multiset<ll>::iterator it;
	FOR(i, 0, a - 1)
	{
		S.insert(A[i]);
		it = S.lower_bound(A[i]);
		it++;
		if (it != S.end()) S.erase(it);
	}
	return S;
}

Some snippets are mine, some are taken from the internet. If you want to add some snippets on the blog, please let me know in the comment section.

You can read more about ordered_set and ordered_multiset here: https://mirror.codeforces.com/blog/entry/11080

Thanks for reading! Hope this can help you.

A little surprise

def binarySearch(arr, key): # search lower bound(key) beg, end = 0, len(arr) - 1 found = False ind = -1 while beg <= end: mid = beg + (end - beg) // 2 # to avoid mid overflow if key == arr[mid]: # condition found = True ind = mid # end = mid - 1 # lower bound break # traditional BS elif key < arr[mid]: end = mid - 1 else: beg = mid + 1 if not found: # insertion point = beg (beg < end == True) return -1 else: return ind

Комментарии (26)

Показать архивные | Написать комментарий?

NOT_a_troll_ftw

2 года назад, # |

+145

→ Ответить

lrvideckis

+51

I prefer kactl's prime test as it's deterministic

blackhatinside

-32

You missed something very important sir. Without that, this blog would be incomplete. Binary Search!

I guess Um_nik would be proud of me on this day :P

karn_07

2 года назад, # ^ |

I guess we can use simple binary_search (start,end,key) function.

Um_nik

+349

Since you thought it is a good idea to tag me: this implementation is an abomination, you should be ashamed of yourself.

adityagamer

+13

ROFL!!! Not everyone is a simp like him

Our um_nik

-is-this-fft-

← Rev. 2 →

+38

Since someone posted an implementation of binary search, I can't not use this opportunity to popularize lifting-style binary search.

int ans = 0;
for (int k = 1 << 29; k != 0; k /= 2)
  if (is_ok(ans + k))
    ans += k;

which finds the greatest integer $$$x$$$ in $$$[0, 2^{30} - 1]$$$ such that is_ok(x) is true (assuming the function is binary-searchable, of course).

hydroshiba

Just wondering, is it better to use OR operation instead of addition? In my template which I copied uses OR instead.

Aaeria

+16

+18

Very likely it is the same; if OR is any faster, the compiler should be smart enough to see that it can be used.

Also, if you do this thing on floating-point numbers (replacing k != 0 with k > EPS), you can't use |= anymore but can use +=.

it also doesn't work if u start at anything other than 0

Dan4Life

+30

When did binary search get so complicated

shreyas_171

+21

Great blog but I prefer conventional way , because it lets me know the code structure during debugging

DestroyCopyright

One short tip that will shorten your time:

You can delete many template <typename T> if you use auto.

Tioz0

← Rev. 3 →

-10

Not quite, the auto isn't that magical. To be more precise auto can only be use with lamda function, and some struct/class variables

ivan100sic

+23

In C++20 you can use it in many more places

chromate00

How about providing ordered set and ordered map instead of ordered multiset? It would be helpful to do this and teach them to use the comparators with equality (less_equal, etc) instead for a multiset. This is an example snippet:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T,class Cmp=less<T>> using ordered_set=tree<T,null_type,Cmp,rb_tree_tag,tree_order_statistics_node_update>;
template<class T,class U,class Cmp=less<T>> using ordered_map=tree<T,U,Cmp,rb_tree_tag,tree_order_statistics_node_update>;

(do note that I made the template format same with std::set and std::map)

nikgaevoy

LIS is obviously wrong.

Countertest

for (auto it: LIS({2, 3, 1}))
	cout << it << ' ';
cout << endl;

Prints "1 3".

thanhchauns2

Yes, I forgot to mention it is used for finding the longest LIS available's length, not itself.

In that case it is better to return S.size(), not the multiset itself. Also, multiset is too excessive here, vector would be just better.

dalex

+102

The shortest implementation I know is this (if you need only the length):

// d = {INF, ... INF (n times)}
for (int x : arr) *lower_bound(d.begin(), d.end(), x) = x;
// length == position of first INF in d

Amazing how this not so easy algorithm is a one-liner.

And upper_bound makes it non-decreasing.

also let me advertise this (probably not so) short snippet which I like to call the "Universal Container Input". Simply said, it lets you use std::cin for almost any iterable container whose value type is one that could be used with std::cin (which, in turn, could be another container type). The only exception is the dynamically allocated array, which I have not found a way. Here's the snippet:

template<class T>struct is_string:public std::disjunction<std::is_same<char *, typename std::decay_t<T>>,std::is_same<const char *, typename std::decay_t<T>>,std::is_same<std::string,typename std::decay_t<T>>>{};
namespace isiter{using std::begin;using std::end;template <class T>auto is_iterable_impl(int)->decltype(begin(std::declval<T&>())!=end(std::declval<T&>()),++std::declval<decltype(begin(std::declval<T&>()))&>(),*begin(std::declval<T&>()),std::true_type{});template<class T>std::false_type is_iterable_impl(...);}
template <class T>using is_iterable=decltype(isiter::is_iterable_impl<T>(0));
template <typename T,typename=typename std::enable_if<is_iterable<T>::value&&!is_string<T>::value>::type>std::istream& operator>>(std::istream& i,T&t){for(auto&k:t)i>>k;return i;}

(oh, and std::string and char* will not use this, in this case the overload is useless and therefore I made them not use this)

oversolver

+11

hard to remember last time I needed to find LIS (except maybe in last 10 years)

about multivectors: c++17 allows to use $$$O(d)$$$ vectors instead of $$$O(d^2)$$$ to define required:

vector a(n, vector(m, vector<int>(k)))

harryzhengipsum

I'm very curious about the gnu c++ segment tree... could someone explain how it works and how to use it?

Блог пользователя thanhchauns2

Hi there!

Scanning/printing the whole vector in a single std::cin/std::cout

Scanning/printing std::pair

Ordered set and ordered multiset

Short declaration of 2D and 3D vectors

Erase repeated neighbor elements

Prime test for large numbers

Longest Increasing Subsequence

Longest Strictly Increasing Subsequence

Scanning/printing the whole vector in a single `std::cin/std::cout`

Scanning/printing `std::pair`