Submission #629196

#	Time	Username	Problem	Language	Result	Execution time	Memory
629196		urd05	Rarest Insects (IOI22_insects)	C++17	100 / 100	75 ms	312 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
 
vector<int> v;
bool in[2000];
bool vis[2000];
int mnv=1;
int val;
int n;
 
void mi(int i) {
    in[i]=true;
    move_inside(v[i]);
}
 
void 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 ret=0;
    for(int i=0;i<n;i++) {
        mi(i);
        int got=pb();
        if (got>1) {
            mo(i);
        }
        else {
            vis[i]=true;
            ret++;
        }
    }
    clean();
    return ret;
}
 
bool isp(int x) {
    x-=mnv;
    vector<int> save;
    vector<int> out;
  int pr=0;
    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 {
          if (pr==x-1&&got==x) {
            out.push_back(i);
          }
            save.push_back(i);
        }
      pr=got;
    }
    clean();
    if (save.size()==x*val) {
        for(int i=0;i<save.size();i++) {
            vis[save[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==cnt) {
                    mo(now);
                }
                else {
                    vis[now]=true;
                    cnt++;
                }
              now++;
            }
            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+(hi-lo>5?1:0))/2;
        if (isp(mid)) {
            lo=mid;
        }
        else {
            hi=mid;
        }
    }
  return lo;
}

Compilation message (stderr)

insects.cpp: In function 'bool isp(int)':
insects.cpp:75:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |     if (save.size()==x*val) {
      |         ~~~~~~~~~~~^~~~~~~
insects.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int i=0;i<save.size();i++) {
      |                     ~^~~~~~~~~~~~
insects.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i=0;i<out.size();i++) {
      |                 ~^~~~~~~~~~~

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