Submission #823590

#TimeUsernameProblemLanguageResultExecution timeMemory
823590sysiaICC (CEOI16_icc)C++17
Compilation error
0 ms0 KiB
//Sylwia Sapkowska #include <bits/stdc++.h> #include “icc.h” #pragma GCC optimize("O3", "unroll-loops") using namespace std; void __print(int x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << "'" << x << "'";} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef LOCAL #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif typedef pair<int, int> T; mt19937 rng(chrono::steady_clock().now().time_since_epoch().count()); int p(int a, int b){ return a + rng() % (b-a+1); } struct Interactor{ int n; set<T>s, f; vector<T>edges; int ptr = 0, cnt = 0; void add(){ if (ptr >= (int)edges.size()) { cerr << cnt << "\n"; cerr << "yay\n"; return; } // cerr << "added ";debug(edges[ptr]); s.insert(edges[ptr]); swap(edges[ptr].first, edges[ptr].second); s.insert(edges[ptr]); ptr++; } Interactor(){ n = 100; // n = 7; debug(n); // edges = {{1, 2}, {1, 3}, {4, 2}, {5, 1}, {6, 3}, {7, 3}}; for (int i = 2; i<=n; i++){ int par = p(1, i-1); edges.emplace_back(i, par); debug(i, par); } add(); } int query(int size_a, int size_b, int a[], int b[]){ cnt++; for (int i = 0; i<size_a; i++){ for (int j = 0; j<size_b; j++){ if (s.find({a[i], b[j]}) != s.end()) return 1; } } return 0; } void setRoad(int a, int b){ if (s.find({a, b}) == s.end()){ assert(false); } else { if (f.find({a, b}) != f.end()){ assert(false); } f.insert({a, b}); f.insert({b, a}); } add(); } } I; struct DSU{ vector<int>rep, sz; DSU(int n){ rep.resize(n+1); iota(rep.begin(), rep.end(), 0); sz.assign(n+1, 1); } int f(int a){ return a == rep[a] ? a : rep[a] = f(rep[a]); } void u(int a, int b){ a = f(a); b = f(b); assert(a != b); if (sz[a] < sz[b]) swap(a, b); rep[b] = a; sz[a] += sz[b]; } }; void run(int n){ //int n as arg // int n = I.n; vector<vector<int>>tab(n+1); DSU dsu(n+1); auto create_groups = [&](int cnt){ for (int rep = 1; rep <= cnt; rep++) tab[rep].clear(); int ptr = 1; vector<int>s(n+1); for (int i = 1; i<=n; i++){ if (dsu.f(i) == i){ s[i] = ptr++; } } for (int i = 1; i<=n; i++){ tab[s[dsu.f(i)]].emplace_back(i); } for (int i = 1; i<=cnt; i++){ debug(i, tab[i]); } }; typedef vector<int> vi; auto comp_to_vert = [&](vi &now){ vector<int>ret; for (auto x: now){ for (auto v: tab[x]){ ret.emplace_back(v); } } return ret; }; auto ask = [&](vector<int>x, vector<int>y){ return query((int)x.size(), (int)y.size(), x.data(), y.data()); }; vi A, B; auto divide = [&](int i){ int mask = 0; for (int p = 0; (1<<p) <= i; p++){ A.clear(); B.clear(); for (int rep = 1; rep <= i; rep++){ if (rep&(1<<p)) A.emplace_back(rep); else B.emplace_back(rep); } if (ask(comp_to_vert(A), comp_to_vert(B))) { mask += (1<<p); } } return mask; }; auto binsearch = [&](int i, int mask){ A.clear(); B.clear(); debug(mask); for (int j = 1; j <= i; j++){ int k = (j^mask); if (j < k && k <= n){ A.emplace_back(j); B.emplace_back(k); } } debug(A); debug(B); vector<int> a = comp_to_vert(A); vector<int> b = comp_to_vert(B); debug(a, b); int ans[2]; for (int rep = 0; rep < 2; rep++){ int l = 0, r = (int)a.size()-1; ans[rep] = r; while (r >= l){ int mid = (l+r)/2; if (ask(vi(a.begin(), a.begin()+mid+1), b)) { ans[rep] = a[mid]; r = mid-1; } else l = mid+1; } swap(a, b); } debug(ans[0], ans[1]); dsu.u(ans[0], ans[1]); setRoad(ans[0], ans[1]); }; for (int i = n; i >= 2; i--){ create_groups(i); binsearch(i, divide(i)); } } // int32_t main(){ run(); }

Compilation message (stderr)

icc.cpp:3:10: error: extended character “ is not valid in an identifier
    3 | #include “icc.h”
      |          ^
icc.cpp:3:10: error: #include expects "FILENAME" or <FILENAME>
    3 | #include “icc.h”
      |          ^~~~
icc.cpp:3:17: error: extended character ” is not valid in an identifier
    3 | #include “icc.h”
      |               ^
icc.cpp: In lambda function:
icc.cpp:144:16: error: 'query' was not declared in this scope
  144 |         return query((int)x.size(), (int)y.size(), x.data(), y.data());
      |                ^~~~~
icc.cpp: In lambda function:
icc.cpp:191:9: error: 'setRoad' was not declared in this scope
  191 |         setRoad(ans[0], ans[1]);
      |         ^~~~~~~