제출 #596022

#제출 시각아이디문제언어결과실행 시간메모리
596022MadokaMagicaFan버섯 세기 (IOI20_mushrooms)C++14
99.56 / 100
14 ms512 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using pi = pair<int,int>; #define all(v) v.begin(),v.end() #define sort(v) sort(all(v)) #define endl '\n' #define forn(i,n) for(int i = 0; i < n; ++i) #define forbe(i,b,e) for(int i = b; i < e; ++i) #define forr(i,n) for(int i = n-1; i >= 0; --i) #define sz(v) ((int)v.size()) #define pb push_back #define f first #define s second mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int S = 84; int use_machine(vi x); int count_mushrooms(int n) { int l, j, i, val, ans = 0, pnt = 3; if (n < 420) { for (i = 2; i < n; i+=2) ans += (2 - use_machine({i-1,0,i})); if ((n&1)==0) ans += (1 - use_machine({n-1,0})); return ans+1; } vi a, b, ask, rm, rem; a.pb(0); for (i = 1; i < n; ++i) rm.pb(i); shuffle(rm.begin(), rm.end(), rng); while (max(sz(a), sz(b)) < 2) { if (use_machine({0,rm.back()})) b.pb(rm.back()); else a.pb(rm.back()); rm.pop_back(); } if (sz(b) > sz(a)) swap(a,b); while (max(sz(a), sz(b)) < 3) { assert(sz(rm) > 1); ask.clear(); i = rm.back(); rm.pop_back(); j = rm.back(); rm.pop_back(); ask = {a[0], i, a[1], j}; val = use_machine(ask); if (val&1) b.pb(j); else a.pb(j); if (val&2) b.pb(i); else a.pb(i); } if (sz(b) > sz(a)) swap(a,b); int cnt = 0; while (cnt < S && sz(b) < 2) { ++cnt; ask.clear(); assert(sz(rm) > 2); i = rm.back(); rm.pop_back(); j = rm.back(); rm.pop_back(); assert(sz(rem) == 0 || sz(rem) == 2); if (sz(rem)) l = rem[0]; else {l = rm.back(); rm.pop_back();} ask = {a[0], i, a[1], j, a[2], l}; val = use_machine(ask); if (val&1) { b.pb(l); if (sz(rem)) a.pb(rem[1]); } else { a.pb(l); if (sz(rem)) b.pb(rem[1]); } rem.clear(); val >>= 1; if (val == 0) { a.pb(i), a.pb(j); } else if (val == 2) { b.pb(i), b.pb(j); } else { rem.pb(i), rem.pb(j); } } shuffle(rm.begin(), rm.end(), rng); int scnt = 0; while (cnt < S) { ++cnt; ++scnt; ask.clear(); assert(sz(rm) > 2); i = rm.back(); rm.pop_back(); j = rm.back(); rm.pop_back(); assert(sz(rem) == 0 || sz(rem) == 2); if (sz(rem)) l = rem[0]; else {l = rm.back(); rm.pop_back();} ask = {a[0], i, a[1], b[0], j, b[1], a[2], l}; val = use_machine(ask)-2; if (val&1) { b.pb(l); if (sz(rem) && scnt==1) a.pb(rem[1]); if (sz(rem) && scnt!=1) b.pb(rem[1]); } else { a.pb(l); if (sz(rem) && scnt==1) b.pb(rem[1]); if (sz(rem) && scnt!=1) a.pb(rem[1]); } rem.clear(); val >>= 1; if (val == 0) { a.pb(i), b.pb(j); } else if (val == 2) { b.pb(i), a.pb(j); } else { rem.pb(i), rem.pb(j); } } if (sz(rem)) { assert(sz(rem)==2);rm.pb(rem[0]), rm.pb(rem[1]); } shuffle(rm.begin(), rm.end(), rng); if (a[0] != 0) swap(a,b); ans = sz(a); while (sz(rm)) { ask.clear(); if (sz(a) > sz(b)) { while (sz(rm) && sz(ask) < (sz(a)<<1)) { ask.pb(a[sz(ask)>>1]); ask.pb(rm.back()); rm.pop_back(); } ans += (sz(ask)>>1); val = use_machine(ask); ans -= ((val+1)>>1); if (val&1) b.pb(ask[sz(ask)-1]); else a.pb(ask[sz(ask)-1]); } else { while (sz(rm) && sz(ask) < (sz(b)<<1)) { ask.pb(b[sz(ask)>>1]); ask.pb(rm.back()); rm.pop_back(); } val = use_machine(ask); ans += ((val+1)>>1); if (val&1) a.pb(ask[sz(ask)-1]); else b.pb(ask[sz(ask)-1]); } } return ans; } #ifdef ONPC vi rans; int cnt = 0; int use_machine(vi x){ ++ cnt; int _ans = 0; /* cout << "ASK: "; */ /* forn(i , sz(x)) */ /* cout << x[i] << ' '; */ /* cout << endl; */ forn(i , sz(x)-1) if (rans[x[i]] != rans[x[i+1]]) ++_ans; /* cout << "ANSWER: " << _ans << endl; */ return _ans; } void solve() { int n; cin >> n; rans.resize(n); char c; int ranswer = 0; forn(i, n) { cin >> c; rans[i]=(c=='A'); if (c=='A') ++ranswer; } int cans = count_mushrooms(n); /* if (cans != ranswer) */ /* forn(i, n) */ /* cout << rans[i] << ' '; */ /* cout << endl; */ /* cout << cans << ' ' << ranswer << endl; */ /* cout << n << ' ' << cnt << endl; */ cout << cnt << endl; } int main(int argc, char **argv) { if (argc > 1) { S = 0; int p = 0; while (argv[1][p] != '\0') S = S * 10 + (argv[1][p++] - '0'); } /* freopen("infile", "r", stdin); */ // ios_base::sync_with_stdio(0);cin.tie(0); solve(); } #endif

컴파일 시 표준 에러 (stderr) 메시지

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:27:32: warning: unused variable 'pnt' [-Wunused-variable]
   27 |     int l, j, i, val, ans = 0, pnt = 3;
      |                                ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...