#include<bits/stdc++.h> #ifndef cpismylifeOwO #include "grader.h" #endif // cpismylifeOwO using namespace std; const long long mod = 1e9 + 7; const int MaxN = 1e6 + 5; #ifdef cpismylifeOwO #define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i) int N; vector <int> v; int L; bool isSubsequence(vector <int> t) { //for (int x : t) cout << x << " "; //cout << "\n"; assert((int) t.size() <= N); L = max(L, (int) t.size()); int cur = 0; for (int i: t) { while (cur < N && v[cur] != i) ++cur; if (cur == N) return false; ++cur; } return true; } #endif // cpismylifeOwO vector<int> rev(vector<int> a, bool sw) { if (sw) { for (int x = 0; x < (int)a.size(); x++) { a[x] ^= 1; } } return a; } struct Change { int prev, p1, p2; Change() = default; Change(int _prev, int _p1, int _p2) { prev = _prev; p1 = _p1; p2 = _p2; } }; int nxt[MaxN]; int F[MaxN][3]; pair<int, int> Fnxt[MaxN][3]; vector<int> findSequence(int n) { vector<int> now, res; now.push_back(0); while ((int)now.size() <= (n / 2) + 1 && isSubsequence(now)) { now.push_back(0); } bool sw = false; int cntleft = 0, cnt2 = 0; if ((int)now.size() > (n / 2) + 1) { sw = true; now.clear(); now.push_back(1); while (isSubsequence(now)) { now.push_back(1); } now.pop_back(); cntleft = n - (int)now.size(); res.push_back(2); cnt2++; for (int x : now) { res.push_back(!x); res.push_back(2); cnt2++; } } else { sw = false; now.pop_back(); cntleft = n - (int)now.size(); res.push_back(2); cnt2++; for (int x : now) { res.push_back(x); res.push_back(2); cnt2++; } } while (cnt2 > 1 && cntleft) { vector<Change> lst2; now.clear(); int cur0 = (int)res.size(), cur1 = cur0; F[(int)res.size()][0] = 0; F[(int)res.size()][1] = 0; F[(int)res.size()][2] = 0; for (int x = (int)res.size() - 1; x >= 0; x--) { nxt[x] = max(cur0, cur1); if (!res[x]) { cur0 = x; } else { cur1 = x; } F[x][0] = F[x][1] = F[x][2] = 1e9; int cnt0 = 0, cnt1 = 0, cntline = 0; bool isp = false, isp2 = (res[0] == 2); for (int y = x; y < (int)res.size(); y++) { cnt0 += (res[y] == 0); cnt1 += (res[y] != 0); cntline += (y == x || ((res[y] == 0) != (res[y - 1] == 0))); isp &= (res[y] != 2); if (cnt0 && (y == (int)res.size() - 1 || res[y + 1] == 1) && F[x][0] > F[y + 1][1] + cnt0) { F[x][0] = F[y + 1][1] + cnt0; Fnxt[x][0] = make_pair(y + 1, 1); } if ((y == (int)res.size() - 1 || res[y + 1] == 1) && F[x][0] > F[y + 1][2] + cnt0) { F[x][0] = F[y + 1][2] + cnt0; Fnxt[x][0] = make_pair(y + 1, 2); } if (!isp2 && cntline) { if (F[x][1] > F[y + 1][0] + cntline - (y == (int)res.size() - 1)) { F[x][1] = F[y + 1][0] + cntline - (y == (int)res.size() - 1); Fnxt[x][1] = make_pair(y + 1, 0); } if (F[x][1] > F[y + 1][2] + cntline - (y == (int)res.size() - 1)) { F[x][1] = F[y + 1][2] + cntline - (y == (int)res.size() - 1); Fnxt[x][1] = make_pair(y + 1, 2); } } if (cnt1 && isp && (y == (int)res.size() - 1 || res[y + 1] == 0)) { if (F[x][2] > F[y + 1][0] + cnt1) { F[x][2] = F[y + 1][0] + cnt1; Fnxt[x][2] = make_pair(y + 1, 0); } if (F[x][2] > F[y + 1][1] + cnt1) { F[x][2] = F[y + 1][1] + cnt1; Fnxt[x][2] = make_pair(y + 1, 1); } } } } int k = max(cur0, cur1), pre = -1; while (k < (int)res.size()) { for (int x = pre + 1; x <= k; x++) { if (res[x] == 2) { lst2.push_back(Change(x - pre, x, (int)now.size() - 1)); } } pre = k; now.push_back(res[k]); k = nxt[k]; } for (int x = pre + 1; x < (int)res.size(); x++) { if (res[x] == 2) { lst2.push_back(Change(x - pre, x, (int)now.size() - 1)); } } int add = 0; for (Change& u : lst2) { vector<int> ask; for (int x = 0; x <= u.p2; x++) { ask.push_back(now[x]); } for (int x = 1; x <= u.prev; x++) { ask.push_back(1); } if (u.p1 + add + 1 < (int)res.size()) { int v = u.p1 + 1; pair<int, int> mi = min(make_pair(F[v][0], 0), min(make_pair(F[v][1], 1), make_pair(F[v][2], 2))); int t = mi.second; while (v + add < (int)res.size()) { int con = Fnxt[v][t].first; if (!t) { for (int x = v + add; x < con + add; x++) { if (res[x] == 0) { ask.push_back(0); } } } else if (t == 1) { for (int x = v + add; x < con + add; x++) { if (x == v + add || ((res[x] > 0) != (res[x - 1] > 0))) { ask.push_back(res[x]); } } if (con + add >= (int)res.size()) { ask.pop_back(); } } else { for (int x = v + add; x < con + add; x++) { if (res[x] == 1) { ask.push_back(1); } } } t = Fnxt[v][t].second; v = con; } } if (isSubsequence(rev(ask, sw))) { res.insert(res.begin() + add + u.p1, 1); add++; cntleft--; } else { res.erase(res.begin() + add + u.p1); add--; cnt2--; } if (cnt2 <= 1 || cntleft == 0) { break; } } } vector<int> tmp = res; res.clear(); for (int x : tmp) { if (x == 2) { for (int y = 1; y <= cntleft; y++) { res.push_back(1); } cntleft = 0; } else { res.push_back(x); } } return rev(res, sw); } #ifdef cpismylifeOwO mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); long long rand(long long l, long long h) { return uniform_int_distribution <long long> (l, h) (rng); } int main(void) { freopen("stub.INP", "r", stdin); //freopen("stub.OUT", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr); bool type, isprinted; cin >> N >> type >> isprinted; v.resize(N); if (!type) { for (int x = 0; x < N; x++) cin >> v[x]; } else REP(i, N) v[i] = rand(0, 1); vector <int> res = findSequence(N); cout << L << '\n'; if (isprinted) { for (int x : v) cout << x << " "; cout << '\n'; for (int x : res) cout << x << ' '; cout << "\n"; } bool chk = ((int)res.size() == N); if (chk) { for (int x = 0; x < N; x++) { chk &= (v[x] == res[x]); } } cout << chk << "\n"; return (0^0); } #endif // cpismylifeOwO

grader.cpp: In function 'int main()':
grader.cpp:28:26: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   28 |     fprintf (fifo_out, "%d\n", ans.size ());
      |                         ~^     ~~~~~~~~~~~
      |                          |              |
      |                          int            std::vector<int>::size_type {aka long unsigned int}
      |                         %ld