Submission #627867

#TimeUsernameProblemLanguageResultExecution timeMemory
627867FischerRarest Insects (IOI22_insects)C++17
100 / 100
59 ms336 KiB
#include <bits/stdc++.h> #include "insects.h" using namespace std; const int maxn = 2010; int in[maxn]; vector<bool> memo; int n, c; int base; vector<int> id; void put(int x) { move_inside(x); //memo[x] = 1; } void pop(int x) { move_outside(x); //memo[x] = 0; } map<vector<bool>, int> mapMemo; bool last[maxn]; int push() { return press_button(); if (mapMemo.count(memo)) return mapMemo[memo]; for (int i = 0; i < n; ++i) { if (last[i] != (in[i] != 0)) { if (last[i]) move_outside(i); else move_inside(i); last[i] ^= 1; } } return mapMemo[memo] = press_button(); } bool p(int x) { int len = base; for (int i:id) { if (in[i] == -1) continue; if (len == x * c) break; put(i); in[i] = 1; if (push() > x) { pop(i); in[i] = 0; } else { len += 1; } } if (len == x * c) { for (int i=0;i<n; ++i) { if (in[i] == 1) { in[i] = -1; base += 1; } } } else { for (int i=0;i<n;++i) { if (in[i] == 1) { pop(i); in[i] = 0; } else { in[i] = -1; } } } return len == x * c; } int min_cardinality(int N) { n = N; id.resize(n); iota(id.begin(), id.end(), 0); random_shuffle(id.begin(), id.end()); memo.assign(n, 0); c = 0; for (int i=0; i<n; ++i) { put(i); in[i] = -1; if (push() == 1) c += 1; else pop(i), in[i] = 0; } base = c; if (c == 1) return N; if (c == N) return 1; int lo = 1, hi = N / c+1; while (hi-lo>1) { int mid = (lo + hi) / 2; if (p(mid)) lo = mid; else hi = mid; } return lo; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...