Submission #1078259

#TimeUsernameProblemLanguageResultExecution timeMemory
1078259Faisal_SaqibRarest Insects (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(); set<int> machine,rem,real_; void add(int x) { if(machine.find(x)==machine.end()) { machine.insert(x); } } void remp(int x) { if(machine.find(x)!=machine.end()) { machine.erase(x); } } map<vector<int>,int> store; int ask() { vector<int> cur(begin(machine),end(machine)); if(store.find(cur)!=store.end()) return store[cur]; for(auto&i:real_) { if(machine.find(i)==machine.end()) { move_outside(i); } } for(auto&i:machine) { if(real_.find(i)==real_.end()) { move_inside(i); } } return store[cur]=press_button(); } int min_cardinality(int n) { add(0); for(int i=1;i<n;i++) { add(i); if(ask()>1) { rem.insert(i); remp(i); } } int sz=machine.size(); int s=1; int e=(n/sz)+1; while(s+1<e) { int mid=(s+e)/2; vector<int> cur; for(auto&i:rem) { if(machine.size()==(sz*mid)) break; add(i); if(ask()>mid) { remp(i); } else { cur.push_back(i); if(machine.size()==(sz*mid)) break; } } if(machine.size()==((sz*mid))) { s=mid; for(auto&i:cur) rem.erase(i); } else{ e=mid; rem.clear(); for(auto&i:cur) { rem.insert(i); remp(i); } } } return s; }

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:65:21: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |    if(machine.size()==(sz*mid))
      |       ~~~~~~~~~~~~~~^~~~~~~~~~
insects.cpp:75:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |     if(machine.size()==(sz*mid))
      |        ~~~~~~~~~~~~~~^~~~~~~~~~
insects.cpp:79:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |   if(machine.size()==((sz*mid)))
      |      ~~~~~~~~~~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...