제출 #1078081

#제출 시각아이디문제언어결과실행 시간메모리
1078081Faisal_Saqib드문 곤충 (IOI22_insects)C++17
0 / 100
1 ms344 KiB
#include <bits/stdc++.h> using namespace std; void move_inside(int i); void move_outside(int i); int press_button(); map<set<int>,int> store; set<int> cur,real_; void add(int i) { i--; cur.insert(i); } void rem(int i) { i--; if(cur.find(i)!=cur.end()) cur.erase(i); } void khatam() { cur.clear(); } int ask() { if(store.find(cur)!=store.end())return store[cur]; for(auto i:cur) { if(real_.find(i)==real_.end()) { real_.insert(i); move_inside(i); } } set<int> rem; for(auto j:real_) { if(cur.find(j)==cur.end()) { rem.insert(j); move_outside(j); } } for(auto i:rem)real_.erase(i); store[cur]=press_button(); // cout<<"asking \n"; // cout<<"For: "; // for(auto i:cur) // { // cout<<i<<' '; // } // cout<<endl; // cout<<"Ans: "<<store[cur]<<endl; return store[cur]; } int min_cardinality(int n) { vector<int> heads={1}; add(1); for(int i=2;i<=n;i++) { add(i); if(ask()==1) heads.push_back(i); else rem(i); } int sz=heads.size(); int s=0; int e=n; while(s+1<e) { int mid=(s+e)/2; khatam(); int sm=0; for(int i=0;i<mid;i++) add(i),sm++; for(int j=mid;j<n;j++) { add(j); if(ask()>mid) { rem(j); } else{ sm++; } } if(sm==((sz*mid))) { s=mid; } else{ e=mid; } } return e; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...