Submission #1009898

#TimeUsernameProblemLanguageResultExecution timeMemory
1009898giorgi123glmCarnival (CEOI14_carnival)C++17
0 / 100
24 ms600 KiB
#include <iostream> #include <vector> #include <algorithm> #include <queue> using namespace std; using std::cout; using std::cin; vector <int> dsu_arr; const int dsu_parent (int p) { return (dsu_arr[p] == p ? p : dsu_arr[p] = dsu_parent (dsu_arr[p])); } inline void dsu_join (int a, int b) { a = dsu_parent (a), b = dsu_parent (b); if (a != b) dsu_arr[b] = a; } inline const pair <int, int> chk (vector <int>& v, int L, int R, int I) { if (L == R) { cout << 2 << ' ' << I << ' ' << v[L] << '\n'; cout.flush (); int t = 0; cin >> t; if (t == 1) dsu_join (I, v[L]); } else { int res1 = 0, res2 = 0; cout << R - L + 1 << ' '; for (int j = L; j <= R; j++) cout << v[j] << ' '; cout << '\n'; cout.flush(); cin >> res1; cout << R - L + 2 << ' '; for (int j = L; j <= R; j++) cout << v[j] << ' '; cout << I << ' '; cout << '\n'; cout.flush(); cin >> res2; if (res1 == 1) for (int j = L + 1; j <= R; j++) dsu_join (v[L], v[j]); if (res2 == 1) dsu_join (v[L], I); else if (res1 == res2) return {L, R}; } return {-1, -1}; } int main () { int n = 0; cin >> n; dsu_arr.resize (n + 1); for (int i = 1; i <= n; i++) dsu_arr[i] = i; vector <bool> checked (n + 1); for (int i = 1; i <= n - 1; i++) { vector <int> v; for (int j = i + 1; j <= n; j++) if (checked[dsu_parent (j)] == 0) v.push_back (j); int n = v.size() - 1; queue <pair <int, int> > q; q.push ({0, n}); while (!q.empty()) { int L = q.back().first, R = q.back().second; q.pop(); if (L == R) chk (v, L, R, i); else { pair <int, int> ret1 = chk (v, L, (L + R) / 2, i); pair <int, int> ret2 = chk (v, (L + R) / 2 + 1, R, i); if (ret1.first != -1) q.push (ret1); if (ret2.first != -1) q.push (ret2); } } checked[i] = 1; } cout << 0 << ' '; for (int i = 1; i <= n; i++) cout << dsu_parent (i) << ' '; cout.flush(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...