Submission #369518

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
369518	2021-02-21 19:37:33	wleung_bvg	Sateliti (COCI20_satellti)	C++17	110 / 110	626 ms	60104 KiB

Main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
template <class C> constexpr int sz(const C &c) { return int(c.size()); }
constexpr const char nl = '\n', sp = ' '; using uint = unsigned int;
using ll = long long; using ull = unsigned long long; using ld = long double;
#if __SIZEOF_INT128__
  using i128 = __int128_t; using ui128 = __uint128_t;
#endif
template <class _T> struct SAISSuffixArray {
  using T = _T;
  static vector<int> SAIS(const vector<int> &S) {
    if (S.empty()) return vector<int>();
    int N = S.size(), K = *max_element(S.begin(), S.end()) + 1;
    vector<bool> isL(N + 1, false); vector<int> ind(N), cnt(K + 1, 0), lms;
    lms.reserve(N); for (auto &&a : S) cnt[a + 1]++;
    partial_sum(cnt.begin(), cnt.end(), cnt.begin());
    isL[N - 1] = true; for (int i = N - 2; i >= 0; i--)
      isL[i] = S[i] == S[i + 1] ? isL[i + 1] : S[i] > S[i + 1];
    auto c = [&] (int i) { return i > 0 && !isL[i] && isL[i - 1]; };
    for (int i = 1; i < N; i++) if (c(i)) lms.push_back(i);
    auto IS = [&] {
      vector<int> tmp(cnt.begin() + 1, cnt.end());
      fill(ind.begin(), ind.end(), -1);
      for (int i = int(lms.size()) - 1; i >= 0; i--)
        ind[--tmp[S[lms[i]]]] = lms[i];
      tmp = vector<int>(cnt.begin(), cnt.end() - 1);
      for (int i = -1, j; i < N; i++)
        if ((j = i < 0 ? N - 1 : ind[i] - 1) >= 0 && isL[j])
          ind[tmp[S[j]]++] = j;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60