제출 #338277

#제출 시각아이디문제언어결과실행 시간메모리
338277MvC버섯 세기 (IOI20_mushrooms)C++17
92.62 / 100
9 ms564 KiB
#include "mushrooms.h" #include <bits/stdc++.h> #define rc(x) return cout<<x<<endl,0 #define pb push_back #define mkp make_pair #define in insert #define er erase #define fd find #define fr first #define sc second #define all(x) x.begin(),x.end() #define lun(x) (int)x.size() typedef long long ll; typedef long double ld; const ll INF=0x3f3f3f3f3f3f3f3f; const ll llinf=(1LL<<60); const int inf=(1<<30); const int nmax=2e4+50; const ll mod=1e9+7; using namespace std; int i,j,t,x,y,rs,k; vector<int>a[2],v; int ask(vector<int> a) { return use_machine(a); } int count_mushrooms(int n) { if(n==2) { if(!ask({0,1}))return 2; return 1; } a[0].pb(0); if(ask({0,1}))a[1].pb(1); else a[0].pb(1); if(ask({0,2}))a[1].pb(2); else a[0].pb(2); k=75; for(i=3;i<n;i+=2) { if(max(lun(a[0]),lun(a[1]))>=k)break; v.clear(); for(j=0;j<2;j++) { if(lun(a[j])<2)continue; v.pb(i),v.pb(a[j][0]); if(i+1<n)v.pb(i+1),v.pb(a[j][1]); x=ask(v); if(!x) { a[j].pb(i); if(i+1<n)a[j].pb(i+1); } else if(x==1) { a[j^1].pb(i); if(i+1<n)a[j].pb(i+1); } else if(x==2) { a[j].pb(i); a[j^1].pb(i+1); } else if(x==3) { a[j^1].pb(i); a[j^1].pb(i+1); } break; } } rs=lun(a[0]); for(;i<n;i+=k) { v.clear(),y=0; if(lun(a[0])>=lun(a[1]))k=lun(a[0]),t=0; else k=lun(a[1]),t=1; for(j=i;j<min(i+k,n);j++) { v.pb(j); v.pb(a[t][j-i]); y++; } x=ask(v); if(x&1)a[t^1].pb(i); else a[t].pb(i); if(t)rs+=(x+1)/2; else rs+=y-(x+1)/2; } return rs; } /*int main() { //freopen("sol.in","r",stdin); //freopen("sol.out","w",stdout); //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0); return 0; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...