Submission #755140

#TimeUsernameProblemLanguageResultExecution timeMemory
755140Rafi22Rarest Insects (IOI22_insects)C++17
99.89 / 100
68 ms428 KiB
#include <bits/stdc++.h> #include "insects.h" using namespace std; #define endl '\n' #define st first #define nd second #define pb push_back #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() #define ll long long ll mod=1000000007; int inf=1000000007; ll infl=1000000000000000007; int ans=1,m; /* int a[107]; map<int,int>ile; set<int>W; void move_inside(int i) { W.insert(i); } void move_outside(int i) { W.erase(i); } int press_button() { ile.clear(); int ans=0; for(auto x:W) ans=max(ans,++ile[a[x]]); return ans; } */ void rek(vector<int>a) { if(sz(a)<m) return ; int k=(sz(a)/m+1)/2; vector<int>T,N; bool is=0; for(auto x:a) { move_inside(x); if(press_button()>ans+k) { move_outside(x); N.pb(x); } else T.pb(x); } if(sz(T)==m*k) { ans+=k; rek(N); } else { for(auto x:T) move_outside(x); rek(T); } } int min_cardinality(int n) { vector<int>V,X; for(int i=0;i<n;i++) { move_inside(i); if(press_button()>1) { move_outside(i); V.pb(i); } else { X.pb(i); m++; } } rek(V); return ans; } /* int main() { int n; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; cout<<min_cardinality(n)<<endl; return 0; } /* 6 5 8 9 5 9 9 */

Compilation message (stderr)

insects.cpp:97:1: warning: "/*" within comment [-Wcomment]
   97 | /*
      |  
insects.cpp: In function 'void rek(std::vector<int>)':
insects.cpp:45:10: warning: unused variable 'is' [-Wunused-variable]
   45 |     bool is=0;
      |          ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...