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"
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
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
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.
This blog is useless for the most part. Oh my, i saved 3 minutes of typing...
I prefer kactl's prime test as it's deterministic
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
I guess we can use simple binary_search (start,end,key) function.
Since you thought it is a good idea to tag me: this implementation is an abomination, you should be ashamed of yourself.
ROFL!!! Not everyone is a simp like him
Since someone posted an implementation of binary search, I can't not use this opportunity to popularize lifting-style binary search.
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).Just wondering, is it better to use OR operation instead of addition? In my template which I copied uses OR instead.
no
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
withk > EPS
), you can't use|=
anymore but can use+=
.it also doesn't work if u start at anything other than 0
When did binary search get so complicated
Great blog but I prefer conventional way , because it lets me know the code structure during debugging
One short tip that will shorten your time:
You can delete many
template <typename T>
if you useauto
.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
In C++20 you can use it in many more places
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:(do note that I made the template format same with
std::set
andstd::map
)LIS is obviously wrong.
Prints "1 3".
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.The shortest implementation I know is this (if you need only the length):
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 withstd::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:(oh, and
std::string
andchar*
will not use this, in this case the overload is useless and therefore I made them not use this)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)$$$
vector
s instead of $$$O(d^2)$$$ to define required:vector a(n, vector(m, vector<int>(k)))
I'm very curious about the gnu c++ segment tree... could someone explain how it works and how to use it?