Submission #982228

#TimeUsernameProblemLanguageResultExecution timeMemory
982228boyliguanhanRarest Insects (IOI22_insects)C++17
100 / 100
36 ms956 KiB
//viewed solution #include "insects.h" #include<bits/stdc++.h> using namespace std; mt19937 rng(random_device{}()); vector<int>ins,notin,notin2; int types,init=0; bool check(int mid){ ins.clear(); notin2.clear(); shuffle(notin.begin(),notin.end(),rng); for(auto i:notin){ if(init==mid*types) { notin2.push_back(i); continue; } move_inside(i); if(press_button()>mid) move_outside(i), notin2.push_back(i); else init++,ins.push_back(i); } return init==mid*types; } int min_cardinality(int N) { for(int i=0;i<N;i++){ move_inside(i); int val=press_button(); if(val-1) notin.push_back(i), move_outside(i); else types++; } if(types==1) return N; int l=1,r=N/types; init=types; while(l<r){ int mid=l+r+1>>1; if(check(mid)){ notin=notin2; l=mid; } else { r=mid-1; for(auto i:ins) move_outside(i),init--; vector<int>bad(N),neni; for(auto i:notin2) bad[i]=1; for(auto i:notin) if(!bad[i]) neni.push_back(i); notin=neni; } } return l; }

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:39:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     int mid=l+r+1>>1;
      |             ~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...