Submission #723499

#	Time	Username	Problem	Language	Result	Execution time	Memory
723499		LittleFlowers__	Rarest Insects (IOI22_insects)	C++17	0 / 100	25 ms	400 KiB

insects

#include<bits/stdc++.h>
#include "insects.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int hmt() {int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';if(n) x=-x;return x;}
#define in hmt()
#define ins ({string x;char c=getchar();for(;c==' '||c=='\n';c=getchar());for(;c!=' '&&c!='\n';c=getchar()) x+=c;x;})
#define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define forb(i,BS) for(int i=BS._Find_first();i< BS.size();i = BS._Find_next(i))
#define timer 1.0*clock()/CLOCKS_PER_SEC
#define forv(a,b) for(auto &a:b)
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define onbit(x,i) (x|(1<<(i-1)))
#define offbit(x,i) (x&~(1<<(i-1)))
int n,m,dd[2010],T=50;
vector<int> a;
/*void move_inside(int i) {cout<<"i "<<i<<endl;}
void move_outside(int i) {cout<<"o "<<i<<endl;}
int press_button() {cout<<"g\n";int x;cin>>x;return x;}*/
int calc(int l,int r,vector<int> e) {
    if(l==r) return e.size()+1;
    int m=(l+r)/2;
    forinc(i,l,m) move_inside(a[i]);
    vector<int> L,R;
    forv(x,e) {
        move_inside(x);
        if(press_button()>1) L.pb(x);
        else R.pb(x);
        move_outside(x);
    }
    forinc(i,l,m) move_outside(a[i]);
    return min(calc(l,m,L),calc(m+1,r,R));
}
bool check(int x) {
    vector<int> e;
    int cnt=m;
    forinc(i,0,n-1) if(!dd[i]) {
        move_inside(i);
        if(press_button()>x+1) {
            move_outside(i);
        } else {
            ++cnt;
            e.pb(i);
        }
    }
    forv(i,e) move_outside(i);
    return cnt<m*(x+1);
}
int min_cardinality(int N) {
    n=N;
    a.clear();
    a.pb(0);
    move_inside(0);
    forinc(i,1,n-1) {
        move_inside(i);
        if(press_button()>1) move_outside(i);
        else a.pb(i);
    }
    reset(dd,0);
    forv(i,a) {
        dd[i]=1;
        forv(i,a) move_outside(i);
    }
    m=a.size();
    if(m<=T) {
        vector<int> e;
        forinc(i,0,n-1) if(!dd[i]) e.pb(i);
        return calc(0,m-1,e);
    } else {
        int l=1,r=n/m,ret;
        while(l<=r) {
            int mid=(l+r)/2;
            if(check(mid)) ret=mid,r=mid-1;
            else l=mid+1;
        }
        return ret;
    }
}
/*int main() {
    cout<<min_cardinality(5);
}*/

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:78:23: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |         int l=1,r=n/m,ret;
      |                       ^~~

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