Submission #830723

#TimeUsernameProblemLanguageResultExecution timeMemory
830723caganyanmazRarest Insects (IOI22_insects)C++17
71.65 / 100
93 ms456 KiB
#include <bits/stdc++.h> #include "insects.h" #define pb push_back using namespace std; //#include "../debug.h" #define debug(x...) void(42) constexpr static int BLOCK = 50; int n; set<int> basis; bool check(int val) { vector<int> ci; for (int i = 0; i < n; i++) { if (basis.find(i) != basis.end()) continue; move_inside(i); ci.pb(i); if (press_button() > val) { ci.pop_back(); move_outside(i); } } bool res = ci.size() == (val - 1) * basis.size(); for (int i : ci) move_outside(i); return res; } int test_a() { int l = 1, r = 1 + (n / basis.size()); debug(l, r); while (r - l > 1) { int m = l+r>>1; debug(m); if(check(m)) l = m; else r = m; } debug(l); return l; } vector<int> bs; set<int> machine; int get_min(int l, int r, vector<int>& v) { if (r - l == 1) { debug(l, v); return v.size()+1; } int m = l+r>>1; for (int i = l; i < m; i++) { if (machine.find(bs[i]) != machine.end()) continue; machine.insert(bs[i]); move_inside(bs[i]); } for (int i = m; i < r; i++) { if (machine.find(bs[i]) == machine.end()) continue; machine.erase(bs[i]); move_outside(bs[i]); } vector<int> lv, rv; for (int i : v) { move_inside(i); if (press_button() > 1) lv.pb(i); else rv.pb(i); move_outside(i); } int lres = get_min(l, m, lv); int rres = get_min(m, r, rv); return min(lres, rres); } int test_b() { for (int i : basis) { bs.pb(i); machine.insert(i); } vector<int> v; for (int i = 0; i < n; i++) if (basis.find(i) == basis.end()) v.pb(i); return get_min(0, bs.size(), v); } int min_cardinality(int N) { n = N; for (int i = 0; i < n; i++) { move_inside(i); if (press_button() > 1) move_outside(i); else basis.insert(i); } if (basis.size() > BLOCK) return test_a(); else return test_b(); }

Compilation message (stderr)

insects.cpp: In function 'int test_a()':
insects.cpp:41:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   int m = l+r>>1;
      |           ~^~
insects.cpp: In function 'int get_min(int, int, std::vector<int>&)':
insects.cpp:61:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |  int m = l+r>>1;
      |          ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...