Submission #835025

#TimeUsernameProblemLanguageResultExecution timeMemory
835025pavementRarest Insects (IOI22_insects)C++17
10 / 100
89 ms508 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; #define pb push_back vector<int> cur_v, perm; int qry(vector<int> v) { sort(v.begin(), v.end()); vector<int> chng; set_symmetric_difference(v.begin(), v.end(), cur_v.begin(), cur_v.end(), back_inserter(chng)); for (int i : chng) { if (binary_search(v.begin(), v.end(), i)) { move_inside(perm[i]); } else { move_outside(perm[i]); } } cur_v = v; return press_button(); } mt19937 rng(998244353); int min_cardinality(int N) { perm.resize(N); iota(perm.begin(), perm.end(), 0); shuffle(perm.begin(), perm.end(), rng); vector<int> rep, cnt(N, 0), lnk(N, -1); for (int i = 0; i < N; i++) { { shuffle(rep.begin(), rep.end(), rng); int lo = 0, hi = (int)rep.size() - 1; while (lo <= hi) { int mid = (lo + hi) / 2; vector<int> cur; for (int j = 0; j <= mid; j++) { cur.pb(rep[j]); } int q1 = qry(cur); cur.pb(i); int q2 = qry(cur); if (q1 != q2) { lnk[i] = rep[mid]; hi = mid - 1; } else { lo = mid + 1; } } } if (lnk[i] != -1) { rep.erase(find(rep.begin(), rep.end(), lnk[i])); } rep.pb(i); } int ret = N; for (int i = N - 1; i >= 0; i--) { cnt[i]++; if (lnk[i] == -1) { ret = min(ret, cnt[i]); } else { cnt[lnk[i]] += cnt[i]; } } return ret; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...