Submission #629122

#	Time	Username	Problem	Language	Result	Execution time	Memory
629122		urd05	Rarest Insects (IOI22_insects)	C++17	0 / 100	1 ms	336 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> v;
bool in[2000];
bool vis[2000];
int mnv;
int val;
int n;

int mi(int i) {
    in[i]=true;
    move_inside(v[i]);
}

int mo(int i) {
    in[i]=false;
    move_outside(v[i]);
}

int pb() {
    return press_button();
}

void clean() {
    for(int i=0;i<n;i++) {
        if (in[i]) {
            mo(i);
        }
    }
}

int f() {
    int pr=0;
    int ret=0;
    for(int i=0;i<n;i++) {
        mi(i);
        int got=pb();
        if (got==pr) {
            mo(i);
        }
        else {
            //vis[i]=true;
            ret++;
            pr=got;
        }
    }
    clean();
    return ret;
}

bool isp(int x) {
    x-=mnv;
    vector<int> in;
    vector<int> out;
    for(int i=0;i<n;i++) {
        if (vis[i]) {
            continue;
        }
        mi(i);
        int got=pb();
        if (got>x) {
            mo(i);
            out.push_back(i);
        }
        else {
            in.push_back(i);
        }
    }
    clean();
    if (in.size()==x*val) {
        for(int i=0;i<in.size();i++) {
            vis[in[i]]=true;
        }
        mnv+=x;
        return true;
    }
    for(int i=0;i<out.size();i++) {
        vis[out[i]]=true;
    }
    return false;
}

int min_cardinality(int N) {
    n=N;
    for(int i=0;i<n;i++) {
        v.push_back(i);
    }
    srand(int(time(NULL)));
    random_shuffle(v.begin(),v.end());
    val=f();
    if (val<4) {
        memset(vis,0,sizeof(vis));
        int sum=n;
        int ret=n;
        for(int i=0;i<val-1;i++) {
            int now=0;
            while (vis[now]) {
                now++;
            }
            mi(now);
            vis[now]=true;
            now++;
            int cnt=1;
            while (now<n) {
                while (now<n&&vis[now]) {
                    now++;
                }
                if (now>=n) {
                    break;
                }
                mi(now);
                int got=pb();
                if (got>=2) {
                    mo(now);
                }
                else {
                    vis[now]=true;
                    cnt++;
                }
            }
            clean();
            ret=min(ret,cnt);
            sum-=cnt;
        }
        return min(sum,ret);
    }
    int lo=1; //ans>=lo
    int hi=n/val+1; //ans<hi
    while (lo+1<hi) {
        int mid=(lo+hi)/2;
        if (isp(mid)) {
            lo=mid;
        }
        else {
            hi=mid;
        }
    }
  return lo;
}

Compilation message (stderr)

insects.cpp: In function 'int mi(int)':
insects.cpp:15:1: warning: no return statement in function returning non-void [-Wreturn-type]
   15 | }
      | ^
insects.cpp: In function 'int mo(int)':
insects.cpp:20:1: warning: no return statement in function returning non-void [-Wreturn-type]
   20 | }
      | ^
insects.cpp: In function 'bool isp(int)':
insects.cpp:72:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |     if (in.size()==x*val) {
      |         ~~~~~~~~~^~~~~~~
insects.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int i=0;i<in.size();i++) {
      |                     ~^~~~~~~~~~
insects.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i=0;i<out.size();i++) {
      |                 ~^~~~~~~~~~~

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