제출 #1186831

#제출 시각아이디문제언어결과실행 시간메모리
1186831owoovoCounting Mushrooms (IOI20_mushrooms)C++20
92.62 / 100
3 ms712 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=75; 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 ans=a.size(); while(cnt<n){ vector<int> q; int xd=0,st=cnt; if(a.size()>=b.size()){ 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; if(ct/2==xd-1){ for(int i=st+1;i<st+xd;i++){ b.push_back(i); } } if(ct/2==0){ for(int i=st+1;i<st+xd;i++){ a.push_back(i); } } ans+=xd-bs; }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); } if(ct/2==xd-1){ for(int i=st+1;i<st+xd;i++){ a.push_back(i); } } if(ct/2==0){ for(int i=st+1;i<st+xd;i++){ b.push_back(i); } } int as=(ct+1)/2; ans+=as; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...