Submission #796376

#	Time	Username	Problem	Language	Result	Execution time	Memory
796376		ln_e	Rarest Insects (IOI22_insects)	C++17	48.13 / 100	177 ms	552 KiB

insects

    #include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho
    #include "insects.h"
    using ll=long long;
    using ld=long double;
    int const INF=1000000005;
    ll const LINF=1000000000000000005;
    ll const mod=1000000007;
    ld const PI=3.14159265359;
    ll const MAX_N=3e5+5;
    ld const EPS=0.00000001;
    #pragma GCC optimize("O3")
    #pragma GCC optimize("Ofast")
    #define f first
    #define s second
    #define pb push_back
    #define mp make_pair
    #define endl '\n'
    #define sz(a) (int)a.size()
    #define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    using namespace std;
    int cnt=0,n,viz[2005],nwviz[2005];
    vector<ll>original;
    ll check(ll mx){
      vector<ll>v;
      for(ll i=0;i<n;i++)
        nwviz[i]=viz[i];
      for(ll i=0;i<n;i++){
         if(v.size()+original.size()==cnt*mx){
          for(ll i=0;i<n;i++)
        viz[i]=nwviz[i];
        for(auto it : v){
          original.pb(it);
        }
        return 0;
      }
        if(viz[i]){
          continue;
        }
        move_inside(i);
        ll x=press_button();
        if(x>mx){
          move_outside(i);
        }else {
          v.pb(i);
          nwviz[i]=1;
        }
        if(v.size()+original.size()==cnt*mx){
          for(ll i=0;i<n;i++)
        viz[i]=nwviz[i];
        for(auto it : v){
          original.pb(it);
        }
        return 0;
      }
      }
      //  cout<<mx<<' '<<v.size()<<' '<<original.size()<<endl;
      if(v.size()+original.size()==cnt*mx){
          for(ll i=0;i<n;i++)
        viz[i]=nwviz[i];
        for(auto it : v){
          original.pb(it);
        }
        return 0;
      }
      for(auto it : v){
        move_outside(it);
      }
      return 1;
    }
    int min_cardinality(int N) {
      vector<ll>v;
     v.pb(0);
     n=N;
     move_inside(0);
     cnt=1;
     viz[0]=1;
     for(ll i=1;i<N;i++){
      move_inside(i);
      ll x=press_button();
      if(x>1){
        move_outside(i);
      }else {
        v.pb(i);
        viz[i]=1;
        cnt++;
      }
     }
     original=v;
     ll l=2,r=N-v.size()+1,ans=1;
     while(l<=r){
      ll mid=(l+r)/2;
      if(check(mid)==0){
        ans=mid;
        l=mid+1;
      }else r=mid-1;
     }
     return ans;
   }

Compilation message (stderr)

insects.cpp: In function 'll check(ll)':
insects.cpp:28:37: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   28 |          if(v.size()+original.size()==cnt*mx){
      |             ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
insects.cpp:47:36: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   47 |         if(v.size()+original.size()==cnt*mx){
      |            ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
insects.cpp:57:34: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   57 |       if(v.size()+original.size()==cnt*mx){
      |          ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 23.13 / 75