Submission #594074

#TimeUsernameProblemLanguageResultExecution timeMemory
594074AA_SurelyLibrary (JOI18_library)C++14
0 / 100
47 ms308 KiB
#include <bits/stdc++.h> #include "library.h" #define FOR(i, x, n) for(int i = x; i < n; i++) #define F0R(i, n) FOR(i, 0, n) #define ROF(i, x, n) for(int i = n - 1; i >= x; i--) #define R0F(i, n) ROF(i, 0, n) #define WTF cout << "WTF" << endl; #define IOS ios_base::sync_with_stdio(0); cin.tie(0); #define F first #define S second #define pb push_back #define ALL(x) x.begin(), x.end() #define RALL(x) x.rbegin(), x.rend() using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; typedef vector<int> VI; typedef vector<LL> VLL; typedef vector<PII> VPII; typedef vector<PLL> VPLL; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int N = 1000 + 7; int n; bool vis[N]; VI qr, opt, ans; int findLeaf() { fill(ALL(qr), 1); F0R(i, n) { qr[i] = 0; //cout << "asking: "; F0R(i, n) cout << qr[i] << ' '; cout << endl; int z = Query(qr); qr[i] = 1; if (z == 1) return i; } return -1; } inline bool get(int x, int l, int r) { fill(ALL(qr), 0); FOR(i, l, r + 1) qr[ opt[i] ] = 1; int g1 = Query(qr); qr[x] = 1; int g2 = Query(qr); return g1 == g2; } int bs(int now, int l = 0, int r = opt.size()) { if (l == r) return opt[l]; int mid = (l + r) >> 1; if (get(now, l, mid)) return bs(now, l, mid); return bs(now, mid + 1, r); } void Solve(int nn) { n = nn; if (n == 1) { cout << 1 << endl; return; } qr.resize(n); int now = findLeaf(); ans.pb(now + 1); F0R(i, n - 1) { vis[now] = 1; qr[now] = 0; opt.clear(); F0R(i, n) if (!vis[i]) opt.pb(i); //cout << "for i = " << i << " and now = " << now + 1 << " opt is "; //for(int on : opt) cout << on + 1 << ' '; cout << endl; int f = bs(now); ans.pb(f + 1); now = f; } //for(int on : ans) cout << on << ' '; cout << endl; Answer(ans); return; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...