Optimalizácie a implementačné triky

Rýchle IO

Stačí cin.tie(0)->sync_with_stdio(0);. Nič viac. cout.tie(0) je zbytočné.

Ak vypisujete viac viac ako $O(1)$ riadkov, nepoužívajte cout << endl;, ale cout << "\n";, keďže to prvé splachuje a často je príčinou TLE.

Vstavané funkcie

Používajte begin(x), end(x), size(x) namiesto x.begin(), ... Funguje to aj na C polia.

Užitočné funkcie ktoré už dúfam poznáte: all_of, find, count, swap, fill, unique, reverse, sort, lower_bound, max_element, next_permutation. Povinne pozrieť https://en.cppreference.com/w/cpp/algorithm (ale lepšie je to vidno na https://cplusplus.com/reference/algorithm/)

Príklad použitia:

sort(begin(pole), end(pole));
pole.resize(unique(begin(pole), end(pole)) - begin(pole));

alebo

set<int> set_pole(begin(pole), end(pole));
vector<int> unique_pole(begin(set_pole), end(set_pole));

auto maxi = *max_element(begin(pole), end(pole));

Vypisovanie štruktúr

Stačia dva operator<< overaloady na vypisovanie všetkého:

// vypisovanie ľubovolného iterovateľného kontajnéru
// bez kolízie voči string a const char* vďaka basic_ostream<A, B> namiesto ostream
template <typename A, typename B, typename C>
basic_ostream<A, B>& operator<<(basic_ostream<A, B>& os, const C& cont) {
    for (auto it = begin(cont); it != end(cont); ++it)
        os << (it == begin(cont) ? "" : " ") << *it;
    return os;
}

// plus vypisovanie pairov a mame aj associatívne kontajnery
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
    return os << '(' << p.first << ", " << p.second << ')';
}

https://codeforces.com/blog/entry/68920

Polia

Skúšali ste niekedy robiť dynamiku? Otrava že. Ale menej ak použijeme C-čkové polia. Ach jaj C++...

int D[100][100][100] = {0};
// ak chceme niečo iné ako 0, pozor, memset nefunguje lebo to robí po bajtoch
fill((int*)begin(a), (int*)end(a), 1e9);

C++ má svoj std::array<T, N>. Celkom nifty štruktúra, lepšie array<int, 3> než tuple<int, int, int>. Nájdite si miesta kde vám to pomôže.

Naspäť na kurz