Submission #627936

#TimeUsernameProblemLanguageResultExecution timeMemory
627936tutisRarest Insects (IOI22_insects)C++17
57.18 / 100
199 ms63108 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; int min_cardinality(vector<int> x) { int N = x.size(); int add2 = 0; int add1 = 0; vector<int>y; int lo, hi; auto cnt = [&](int c)->int { vector<int>v; y = {}; int k = 0; for (int i : x) { v.push_back(i); move_inside(i); k = press_button(); if (k + add1 == c + 1) { v.pop_back(); move_outside(i); y.push_back(i); } } int r = v.size(); for (int i : v) move_outside(i); return add2 + r; }; int c = cnt(1); if (c * 2 > N) return 1; { x = y; add2 = c; add1 = 1; } lo = 1; hi = N / c; double bias = 3.2; vector<vector<pair<double, int>>>dp(hi + 1, vector<pair<double, int>>(hi + 1)); for (int sz = 1; sz <= hi; sz++) { for (int l = 1; l + sz - 1 <= hi; l++) { int r = l + sz - 1; if (sz == 1) dp[l][r] = {0, l}; else { int m0 = l + 1; int m1 = r; int m = round((l * bias + r * 1.0) / (bias + 1)); auto f = [&](int x) { x = max(x, l + 1); x = min(x, r); return max(dp[l][x - 1].first, dp[x][r].first); }; for (int x = dp[l][r - 1].second; x <= dp[l + 1][r].second; x++) { if (f(x) <= f(m)) m = x; } m = max(m, l + 1); m = min(m, r); dp[l][r].first = f(m) + N - lo * c; dp[l][r].second = m; } } } while (lo < hi) { int m = dp[lo][hi].second; if (hi - lo + 1 >= 64) m = round((lo * bias + hi * 1.0) / (bias + 1)); m = max(m, lo + 1); m = min(m, hi); int k = cnt(m); if (k == m * c) { lo = m; x = y; add2 = m * c; add1 = m; } else hi = m - 1; } return lo; } int min_cardinality(int N) { vector<int>v; for (int i = 0; i < N; i++) v.push_back(i); return min_cardinality(v); }

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(std::vector<int>)':
insects.cpp:54:21: warning: unused variable 'm0' [-Wunused-variable]
   54 |                 int m0 = l + 1;
      |                     ^~
insects.cpp:55:21: warning: unused variable 'm1' [-Wunused-variable]
   55 |                 int m1 = r;
      |                     ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...