Submission #1173235

#TimeUsernameProblemLanguageResultExecution timeMemory
1173235daveleRarest Insects (IOI22_insects)C++20
99.95 / 100
15 ms440 KiB
#ifndef davele #include "insects.h" #endif // davele #include <bits/stdc++.h> //#define int long long #define pii pair<int, int> #define fi first #define se second #define vi vector <int> #define pq priority_queue #define MASK(i) (1ll<<(i)) #define BIT(x, i) (((x) >> (i)) & 1) #define x0 ___x0 #define y0 ___y0 #define div ___div #define next ___next #define prev ___prev #define left ___left #define right ___right #define pos pisosi #define pb push_back #define pf push_front using namespace std; //const int mod = ; //void add (int &a, const int&b){ // a+=b; // if (a>=mod) a-=mod; //} // //void sub (int&a, const int&b){ // a-=b; // if (a<0) a+=mod; //} // //void mul (int&a, const int&b){ // a*=b; // a%=mod; //} template<class X, class Y> bool minimize(X &x, const Y&y){ if (x<=y) return false; else{ x = y; return true; } } template<class X, class Y> bool maximize (X &x, const Y&y){ if (x>=y) return false; else{ x = y; return true; } } //////////////////////////////////////////////////////////////////////////// const int lim = 2e3, limit = lim+5; int n, inMachine[limit], ini[limit], old[limit]; bool banned[limit], curbanned[limit]; #ifdef davele int cnti, cnto, cntp; int A[limit], ts[limit]; void move_inside( int i ){ cnti++; // cerr<<"i "<<i<<"\n"; ts[A[i]]++; } void move_outside (int i){ cnto++; // cerr<<"o "<<i<<"\n"; ts[A[i]]--; } int press_button(){ cntp++; // cerr<<"p \n"; int ret = 1; for (int i=0; i<=lim; i++) maximize (ret, ts[i]); return ret; } #endif // davele int min_cardinality (int N){ n = N; // int numDiff = 0; for (int i=0; i<n; i++){ banned[i] = false; move_inside(i); if (press_button()>1){ move_outside(i); inMachine[i] = false; ini[i] = false; } else{ ini[i] = true; numDiff++; inMachine[i] = true; } } // cerr<<numDiff<<"\n"; int numCur = numDiff; // int left = 1, right = N/numDiff, ret = 1; int loop = 0; while (left<=right){ loop ++; int mid = (left+right)/2; int num = numCur; for (int i=0; i<n; i++) curbanned[i] = banned[i]; for (int i=0; i<n; i++) old[i] = inMachine[i]; for (int i = 0; i < n; i++){ if (numCur == numDiff*mid) break; if (inMachine[i] || banned[i]) continue; move_inside(i); numCur++; inMachine[i] = true; // cerr<<press_button()<<"\n"; if (press_button()>mid){ move_outside(i); numCur--; inMachine[i] = false; curbanned[i] = true; } } // cerr<<mid<<" "<<numCur<<" "<<numDiff<<"\n"; if (numCur==(numDiff*mid)){ ret = mid; left = mid+1; } else{ right = mid-1; for (int i=0; i<n; i++){ if (inMachine[i] && !old[i]) move_outside(i); inMachine[i] = old[i]; } for (int i=0; i<n; i++) banned[i] = curbanned[i]; numCur = num; } } // cerr<<"loop "<<loop<<"\n"; return ret; } /* signed main(){ freopen("insects.inp", "r", stdin); freopen("insects.out", "w", stdout); int n; cin>>n; for (int i=0; i<n; i++) cin>>A[i]; cout<<min_cardinality(n); cerr<<"inside "<<cnti<<" outside "<<cnto<<" press "<<cntp<<"\n"; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...