제출 #631177

#제출 시각아이디문제언어결과실행 시간메모리
631177garam1732드문 곤충 (IOI22_insects)C++17
82.18 / 100
116 ms612 KiB
#include "insects.h" #include <iostream> #include <vector> #include <stack> #include <set> #include <algorithm> #include <cassert> #define ff first #define ss second using namespace std; typedef pair<int, int> pi; //vector<int> ans; //stack<pi> S, v; vector<int> v, w, u[2020]; set<int> s; int min_cardinality(int N) { // v.clear(); w.clear(); s.clear(); // for(int i = 0; i < 2020; i++) u[i].clear(); int num = 0; for(int i = 0; i < N; i++) { move_inside(i); num++; if(press_button() > 1) { move_outside(i); num--; s.insert(i); } } //cout<<num<<endl; int sum = num; int lb = 1, ub = N, mid; while(lb < ub) { for(int i : s) { move_inside(i); u[press_button()].push_back(i); sum++; } while(lb < ub) { mid = (lb*2+ub+2)/3; // for(int i = lb; i <= ub+1; i++) { // cout<<i<<" : "; // for(int t:u[i])cout<<t<<" "; // cout<<endl; // } // cout<<endl; for(int i = ub+1; i > mid; i--) { for(int t : u[i]) { move_outside(t); sum--; } } //assert(press_button() == mid); for(int i = mid+1; i <= ub+1; i++) { for(int t : u[i]) { move_inside(t); if(press_button() > mid) { move_outside(t); w.push_back(t); } else { sum++; u[mid].push_back(t); } } } if(sum == mid*num) { for(int i = lb+1; i <= mid; i++) for(int t : u[i]) s.erase(t); for(int i = lb+1; i <= ub+1; i++) u[i].clear(); lb = mid; w.clear(); break; } else { for(int t : w) s.erase(t); // for(int t : u[mid]) move_outside(t); // sum -= u[mid].size(); for(int i = mid+1; i <= ub+1; i++) u[i].clear(); w.clear(); ub = mid-1; } } } return lb; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...