Submission #1058150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058150		hirayuu_oj	Rarest Insects (IOI22_insects)	C++17	59.61 / 100	77 ms	1008 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;

int min_cardinality(int N) {
    vector<int> types;
    vector<bool> mark(N,false);
    rep(i,N) {
        move_inside(i);
        if(press_button()==1) {
            mark[i]=true;
            types.emplace_back(i);
        }
        else move_outside(i);
    }
    if(types.size()==1)return N;
    vector<int> cnt(types.size(),1);
    vector<vector<array<int,3>>> ser(types.size()+1);
    rep(i,N) {
        if(!mark[i])ser[types.size()/2].push_back({i,(int)types.size(),0});
    }
    int rest=N-types.size();
    int pos=types.size();
    while(rest) {
        for(auto data:ser[pos]) {
            int mid=pos;
            int ok=data[1];
            int ng=data[2];
            move_inside(data[0]);
            if(press_button()==2) {
                ok=mid;
            }
            else {
                ng=mid;
            }
            move_outside(data[0]);
            if(abs(ok-ng)==1) {
                cnt[ok-1]++;
                rest--;
            }
            else {
                ser[(ok+ng)/2].push_back({data[0],ok,ng});
            }
        }
        ser[pos].clear();
        pair<int,int> near={998244353,-1};
        rep(i,types.size()+1) {
            if(ser[i].size())near=min(near,{abs(pos-i),i});
        }
        if(near.second<pos) {
            pos--;
            move_outside(types[pos]);
        }
        else {
            move_inside(types[pos]);
            pos++;
        }
    }
    int ans=998244353;
    for(int i:cnt)ans=min(ans,i);
    return ans;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,n) for(int i=0; i<(n); i++)
      |                                ^
insects.cpp:51:9: note: in expansion of macro 'rep'
   51 |         rep(i,types.size()+1) {
      |         ^~~

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