Submission #1064218

#TimeUsernameProblemLanguageResultExecution timeMemory
1064218MarwenElarbiRarest Insects (IOI22_insects)C++17
59.66 / 100
98 ms1272 KiB
#include <bits/stdc++.h> #include "insects.h" using namespace std; #define pb push_back #define ll long long #define fi first #define se second mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int nax=2005; int sz[nax]; vector<int> insects; vector<int> to_do[nax]; int ls=0; int rs=-1; int c=0; void daq(int l,int r){ if(l==r){ sz[l]+=to_do[l].size(); return; } int mid=(r+l)/2; while(ls<l){ c--; move_outside(insects[ls++]); } while(ls>l){ c++; move_inside(insects[--ls]); } while(rs<mid){ c++; move_inside(insects[++rs]); } while(rs>mid){ c--; move_outside(insects[rs--]); } vector<int> left,right; for(auto u:to_do[mid]){ move_inside(u); int a=press_button(); if(a==2) left.pb(u); else right.pb(u); move_outside(u); } to_do[(mid+l)/2]=left; to_do[(mid+1+r)/2]=right; if(to_do[(mid+l)/2].size()) daq(l,mid); if(to_do[(mid+1+r)/2].size()) daq(mid+1,r); return; } int min_cardinality(int N){ int n=N; move_inside(0); insects.pb(0); int cnt=1; vector<int> cur; for (int i = 1; i < n; ++i) { move_inside(i); cnt++; int a=press_button(); if(a==2){ if(cnt<=2) sz[0]++; else{ cur.pb(i); } move_outside(i); cnt--; }else{ insects.pb(i); } } for(auto u:cur) to_do[(insects.size()-1)/2].pb(u); for (int i = 0; i < insects.size(); ++i) { move_outside(insects[i]); } daq(0,insects.size()-1); int mn=1e9; for (int i = 0; i < insects.size(); ++i) { mn=min(mn,sz[i]); } return mn+1; }

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:75:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for (int i = 0; i < insects.size(); ++i)
      |                   ~~^~~~~~~~~~~~~~~~
insects.cpp:81:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for (int i = 0; i < insects.size(); ++i)
      |                   ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...