Submission #1186818

#TimeUsernameProblemLanguageResultExecution timeMemory
1186818owoovoCounting Mushrooms (IOI20_mushrooms)C++20
63.66 / 100
3 ms632 KiB
#include "mushrooms.h" #include<bits/stdc++.h> #define F first #define S second using namespace std; int p[20010]; int query(vector<int> vc){ vector<int> ask=vc; for(auto &x:ask){ x=p[x]; } return use_machine(vc); } int count_mushrooms(int n) { for(int i=0;i<n;i++)p[i]=i; random_shuffle(&p[1],&p[n]); vector<int> a={0},b; if(n<=226){ int ans=1; for(int i=1;i<n;i++){ if(query({0,i})==0)ans++; } return ans; } int cnt=1; // if(query({0,cnt})==0){ // a.push_back(cnt); // }else{ // b.push_back(cnt); // } // cnt++; // if(query({0,cnt})==0){ // a.push_back(cnt); // }else{ // b.push_back(cnt); // } // cnt++; // int T=70; // if(a.size()>b.size()){ // for(int i=0;i<T;i++){ // int u=query({cnt,a[0],cnt+1,a[1]}); // if(u&1){ // b.push_back(cnt); // }else{ // a.push_back(cnt); // } // if(u&2){ // b.push_back(cnt+1); // }else{ // a.push_back(cnt+1); // } // cnt+=2; // } // }else{ // for(int i=0;i<T;i++){ // int u=query({cnt,b[0],cnt+1,b[1]}); // if(u&1){ // a.push_back(cnt); // }else{ // b.push_back(cnt); // } // if(u&2){ // a.push_back(cnt+1); // }else{ // b.push_back(cnt+1); // } // cnt+=2; // } // } int mx=200; int ans=a.size(); while(cnt<n){ vector<int> q; int xd=0,st=cnt; if(a.size()>=b.size()){ int need=0; if(a.size()<mx){ if(a.size()>=3)need=1; for(int i=0;i<min((int)a.size(),3);i++){ if(cnt<n){ xd++; q.push_back(cnt); cnt++; } q.push_back(a[i]); } }else{ for(int i=0;i<a.size();i++){ if(cnt<n){ xd++; q.push_back(cnt); cnt++; } q.push_back(a[i]); } } int ct=query(q); if(ct%2==0){ a.push_back(st); }else{ b.push_back(st); } int bs=(ct+1)/2; int ok=0; if(ct/2==xd-1){ ok=1; for(int i=st+1;i<st+xd;i++){ b.push_back(i); } } if(ct/2==0){ ok=1; for(int i=st+1;i<st+xd;i++){ a.push_back(i); } } if(ok==0&&need==1){ if(query({0,st+1})==1){ b.push_back(st+1); a.push_back(st+2); }else{ a.push_back(st+1); b.push_back(st+2); } } ans+=xd-bs; }else{ int need=0; if(b.size()<mx){ if(b.size()>=3)need=1; for(int i=0;i<min((int)b.size(),3);i++){ if(cnt<n){ xd++; q.push_back(cnt); cnt++; } q.push_back(b[i]); } }else{ for(int i=0;i<b.size();i++){ if(cnt<n){ xd++; q.push_back(cnt); cnt++; } q.push_back(b[i]); } } int ct=query(q); if(ct%2==0){ b.push_back(st); }else{ a.push_back(st); } int as=(ct+1)/2; int ok=0; if(ct/2==xd-1){ ok=1; for(int i=st+1;i<st+xd;i++){ a.push_back(i); } } if(ct/2==0){ ok=1; for(int i=st+1;i<st+xd;i++){ b.push_back(i); } } if(ok==0&&need==1){ if(query({0,st+1})==1){ b.push_back(st+1); a.push_back(st+2); }else{ a.push_back(st+1); b.push_back(st+2); } } ans+=as; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...