Submission #1078088

#TimeUsernameProblemLanguageResultExecution timeMemory
1078088Faisal_SaqibRarest Insects (IOI22_insects)C++17
50.04 / 100
1163 ms53368 KiB
#include <bits/stdc++.h> using namespace std; void move_inside(int i); void move_outside(int i); int press_button(); map<vector<int>,int> store; vector<int> cur,real_; void add(int i) { i--; cur.push_back(i); } void rem(int i) { i--; cur.pop_back(); } void khatam() { cur.clear(); } int ask() { if(store.find(cur)!=store.end())return store[cur]; for(auto&i:cur) { if(!binary_search(begin(real_),end(real_),i)) { move_inside(i); } } for(auto&j:real_) { if(!binary_search(begin(cur),end(cur),j)) { move_outside(j); } } real_=cur; 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=1; int e=n+1; while(s+1<e) { int mid=(s+e)/2; khatam(); int sm=0; for(int i=1;i<=mid;i++) add(i),sm++; for(int j=mid+1;j<=n;j++) { add(j); if(ask()>mid) { rem(j); } else{ sm++; } } if(sm==((sz*mid))) { s=mid; } else{ e=mid; } } return s; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...