Submission #994953

#TimeUsernameProblemLanguageResultExecution timeMemory
994953NintsiChkhaidzeLibrary (JOI18_library)C++17
100 / 100
212 ms452 KiB
#include "library.h" #include <bits/stdc++.h> #define ll long long #define ull unsigned long long #define pb push_back using namespace std; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll rnd(ll B) { return (ull)rng() % B; } int n; void Solve(int N){ n = N; vector<int> ans(N),fix(N),del(N); for(int i = 0; i < N; i++) { ans[i] = fix[i] = 0; } int cnt = 0,tot = N; while (tot > 0){ int k; while (1){ k = rnd(N); if (del[k]) continue; break; } tot -= 1; del[k] = 1; vector <int> M(N); for (int i=0;i<N;i++) M[i] = 1; M[k] = 0; int A = 1; if (N > 1) A = Query(M); if (A == 1) { fix[k] = 1; ans[0] = k; break; } } for (int i = 0; i + 1 < N; i++){ vector <int> vec; for (int j = 0; j < N; j++){ if (fix[j]) continue; vec.pb(j); } int l = 0, r = vec.size() - 1; int res=0; for (int j = 0; j < 10; j++){ if (l > r) break; vector <int> M(N); int mid = (l + r)/2; for (int w=0;w<N;w++) M[w]=0; for (int w = l; w <= mid; w++) M[vec[w]] = 1; M[ans[i]] = 1; int A = Query(M); M[ans[i]] =0 ; int B = Query(M); if (A == B){ res = mid; r = mid - 1; }else{ l = mid + 1; } } int find = vec[res]; fix[find] = 1; ans[i + 1] = find; } for (int i=0;i<N;i++) ans[i] += 1; Answer(ans); }

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:24:6: warning: unused variable 'cnt' [-Wunused-variable]
   24 |  int cnt = 0,tot = N;
      |      ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...