Submission #1225538

#TimeUsernameProblemLanguageResultExecution timeMemory
1225538mychecksedadLibrary (JOI18_library)C++20
0 / 100
16 ms420 KiB
#include "library.h" #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; using namespace std; int query(vi x){ int num = 0; for(int i = 0; i < x.size(); ++i) num += x[i] != 0; if(num == 0) return 0; return Query(x); } void Solve(int n) { vector<int> X(n); if(n == 1){ Answer(vi{1}); return; } vector<vi> has(n); vi go(n, -1); for(int i = 0; i < n; ++i){ int l = 0, r = n - 1, fine = -1; while(l <= r){ int mid = l+r>>1; for(int j = 0; j < n; ++j) X[j] = (j <= mid ? 1 : 0); for(int y: has[i]) X[y] = 0; X[i] = 0; int num = query(X); X[i] = 1; int num2 = query(X); if(num + 1 != num2){ fine = mid; r = mid - 1; }else{ l = mid + 1; } } if(fine == -1){ continue; } go[i] = fine; has[go[i]].pb(i); } vector<vi> g(n); for(int i = 0; i < n; ++i){ if(go[i] == -1) continue; g[go[i]].pb(i); g[i].pb(go[i]); } int root = 0; for(int i = 0; i < n; ++i) if(g[i].size() == 1) root = i; int v = root; vi res; res.pb(root); int last = -1; for(int i = 1; i < n; ++i){ if(g[v][0] == last){ last = v; v = g[v][1]; }else{ last = v; v = g[v][0]; } res.pb(v); } // for(int x: res) cerr << x + 1 << ' '; // cerr << '\n'; // for(int i = 1; i <= n; ++i){ // cerr << go[i - 1] << ' '; // } for(int &x: res) ++x; Answer(res); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...