Submission #837435

#TimeUsernameProblemLanguageResultExecution timeMemory
837435NothingXDRarest Insects (IOI22_insects)C++17
55.93 / 100
143 ms484 KiB
#include "insects.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; void debug_out(){cerr<<endl;} template<typename Head, typename... Tail> void debug_out(Head H, Tail... T){ cerr << H << ' '; debug_out(T...); } #define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__) #define F first #define S second #define all(x) x.begin(), x.end() #define MP(x, y) make_pair(x, y) const int maxn = 2e3 + 10; const int lg = 20; int l[maxn], r[maxn], cnt[maxn]; vector<int> a, b; vector<int> idx[maxn]; bool check_empty(int x){ for (int i = x; i < a.size(); i++){ if (!idx[i].empty()) return false; } return true; } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int min_cardinality(int N) { int n = N; vector<int> A; for (int i = 0; i < n; i++) A.push_back(i); shuffle(all(A), rng); for (auto i: A){ move_inside(i); if (press_button() == 2){ move_outside(i); l[b.size()] = -1; r[b.size()] = a.size(); b.push_back(i); continue; } //debug(i); a.push_back(i); } for (int i = 0; i < a.size(); i++){ move_outside(a[i]); } for (int i = 0; i < b.size(); i++){ if (l[i] + 1 < r[i]){ int mid = (l[i] + r[i]) >> 1; idx[mid].push_back(i); } } //debug(a.size(), b.size()); while(!check_empty(0)){ int j; for (j = 0; !check_empty(j) && j < a.size(); j++){ move_inside(a[j]); for (auto x: idx[j]){ move_inside(b[x]); // debug(j, x, b[x], press_button()); if (press_button() == 2) r[x] = j; else l[x] = j; if (l[x] + 1 < r[x]){ int mid = (l[x] + r[x]) >> 1; idx[mid].push_back(x); } move_outside(b[x]); } idx[j].clear(); } //for (int i = 0; i < b.size(); i++) debug(i, l[i], r[i]); for (int i = 0; i < j; i++){ move_outside(a[i]); } } for (int i = 0; i < b.size(); i++){ cnt[r[i]]++; } int ans = n; for (int i = 0; i < a.size(); i++){ ans = min(ans, cnt[i]); // debug(cnt[i]); } return ans+1; }

Compilation message (stderr)

insects.cpp: In function 'bool check_empty(int)':
insects.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for (int i = x; i < a.size(); i++){
      |                  ~~^~~~~~~~~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for (int i = 0; i < a.size(); i++){
      |                  ~~^~~~~~~~~~
insects.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for (int i = 0; i < b.size(); i++){
      |                  ~~^~~~~~~~~~
insects.cpp:67:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for (j = 0; !check_empty(j) && j < a.size(); j++){
      |                                  ~~^~~~~~~~~~
insects.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for (int i = 0; i < b.size(); i++){
      |                  ~~^~~~~~~~~~
insects.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for (int i = 0; i < a.size(); i++){
      |                  ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...