Submission #628871

#	Time	Username	Problem	Language	Result	Execution time	Memory
628871		welleyth	Rarest Insects (IOI22_insects)	C++17	60.60 / 100	188 ms	384 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int CNTQ[3] = {};
int getQ(){
    return max(CNTQ[0],max(CNTQ[1],CNTQ[2]));
}

int min_cardinality(int N) {
//    for(int i = 0; i < 50; i++){
//        cout << i+1 << " " << i+1 << " ";
//    }
//    cout << "\n";
//    return 0;
    int col[N];
    for(int i = 0; i < N; i++) col[i] = 0;
    int c = 0;
    int mn = N;
    int pos[N+1];
    bool was[N];
    int pref[N+1];
    for(int i = 0; i <= N; i++) pos[i] = -1;
    for(int i = 0; i < N; i++) was[i] = false;
    for(int i = 0; i < N; i++) pref[i] = -1;
    bool in[N];
    vector<int> order;
    for(int i = 0; i < N; i++){
        move_inside(i);
        if(press_button() == 1){
            was[i] = 1;
            pref[i] = order.size();
            order.push_back(i);
        } else {
            if(i)
                pref[i] = pref[i-1];
            move_outside(i);
        }
    }
    sort(order.begin(),order.end());
    c = order.size();
    for(int i = 0; i < order.size(); i++){
        col[order[i]] = i;
        pos[col[order[i]]] = order[i];
        in[i] = 1;
    }
    if(2*c > N){
        return 1;
    }
//    cerr << "ok\n";
//    for(int i = 0; i < c; i++){
//        cerr << "pos[i] = " << pos[i] << "\n";
//    }
    for(int bt = 0; (1 << bt) < c; bt++){
        for(int i = 0; i < c; i++){
            if(pos[i] == -1)
                continue;
            if(i >> bt & 1 && !in[i]){
                in[i] = 1;
                move_inside(pos[i]);
            }
            if((i >> bt & 1) == 0 && in[i]){
                move_outside(pos[i]);
                in[i] = 0;
            }
        }
        for(int i = 0; i < N; i++){
            if(was[i] || pref[i] < (1 << bt))
                continue;
            move_inside(i);
            int szIn = press_button();
            assert(szIn < 3);
            if(szIn == 2){
                col[i] |= (1 << bt);
            }
            move_outside(i);
        }
        map<int,int> cnt;
        for(int i = 0; i < N; i++){
            if(col[i] >= (1 << bt))
                continue;
            cnt[col[i]]++;
        }
//        cerr << "col: ";
//        for(int i = 0; i < N; i++){
//            cerr << col[i] << " ";
//        }
//        cerr << "\n";
        for(auto&[x,y] : cnt)
            mn = min(mn,y);
        if(mn == 1)
            return 1;
    }
    map<int,int> cnt;
    for(int i = 0; i < N; i++){
        cnt[col[i]]++;
    }
    for(auto&[x,y] : cnt)
        mn = min(mn,y);
    return mn;
}
/**
6
5 8 9 5 9 9

1 2 3 0 0 0

40
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20

100
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50

10
1 0 2 0 3 0 4 0 5 0

1
1

**/

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0; i < order.size(); i++){
      |                    ~~^~~~~~~~~~~~~~

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