Submission #640830

#TimeUsernameProblemLanguageResultExecution timeMemory
640830blueRarest Insects (IOI22_insects)C++17
87.70 / 100
106 ms472 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; #define sz(x) int(x.size()) const int mx = 2'000; vi ins(mx, 0); int ct = 0; int getRandom(int l, int r) { return rand() % (r-l+1); } void move_in(int i) { // cerr << "insert " << i << '\n'; if(ins[i]) return; ins[i] = 1; move_inside(i); ct++; } void move_out(int i) { // cerr << "erase " << i << '\n'; if(!ins[i]) return; ins[i] = 0; move_outside(i); ct--; } int Z = 0; //number of species void solve(vi lst, int b) //b = basic value { if(sz(lst) < Z) return; int mx = sz(lst)/Z; int med = mx/2 + 4; while(med > mx) med--; while(med <= 0) med++; vi ins, notins; int to_exc = -1; bool flag = 0; for(int i : lst) { if(ct == (med + b) * Z) { notins.push_back(i); continue; } move_in(i); int pb = press_button(); if(pb - b > med) { move_out(i); notins.push_back(i); } else { if(pb - b == med && flag == 0) { to_exc = i; flag = 1; } ins.push_back(i); } } if(ct == (med + b) * Z) { solve(notins, b + med); } else { for(int i : ins) move_out(i); vi new_ins; for(int i : ins) if(i != to_exc) new_ins.push_back(i); solve(new_ins, b); } } int min_cardinality(int N) { vi lst; for(int i = 0; i < N; i++) { move_in(i); if(press_button() >= 2) { move_out(i); lst.push_back(i); } else Z++; } solve(lst, 1); return ct / Z; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...