Submission #838242

#	Time	Username	Problem	Language	Result	Execution time	Memory
838242		Dremix10	Rarest Insects (IOI22_insects)	C++17	25 / 100	231 ms	432 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
const int N = 3e5+5;
const int MOD = 1e9+7;
const ll INF = 1e18+5;
#ifdef dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v<<", ";cerr<<"}"<<endl;
    #define p2(x,y) cerr<<#x<<","<<#y<<" = "<<x<<" ,"<<y<<endl;
#else
    #define p(x) {}
    #define pv(x) {}
    #define p2(x,y) {}
#endif



int min_cardinality(int n) {

    int i,ret = 1;
    vector<int> p1,p2,p3;


    /// do some optimization
    multiset<int> s;
        int curr = 0;
        //s.insert(0);
        //move_inside(0);
        bool in[n];
        //p2(1,0)
        int arr[n];
        int j;

    for(i=0;i<n;i++){
        move_inside(i);
        int x = press_button();
        if(x == 1){
            p1.push_back(i);
            s.insert(curr);
            curr++;
            in[i] = true;
            arr[i] = curr-1;
        }
        else{
            assert(x == 2);
            p2.push_back(i);
            move_outside(i);
        }
    }

    int uni = p1.size();

    int sq = sqrt(n);

    if(uni >= 18){

        while(1){


            /// we have p1 with all the colors (uniquely)
            vector<int> neo;
            pv(p1)
            pv(p2)

            for(auto v : p2){
                move_inside(v);
                int x = press_button();
                if(x == ret + 1){
                    neo.push_back(v);
                }
                else{
                    assert(x == ret + 2);
                    p3.push_back(v);
                    move_outside(v);
                }
            }

            p2 = neo;
            pv(p2)
            pv(p3)
            /// we have p2 with all colors that have +1 occurence
            assert(p2.size() <= p1.size());
            if(p2.size() < p1.size())return ret;
            ret ++;

            /// in the machine atm there are all of the colours 2 times each

            p1 = p2;
            p2 = p3;
            p3.clear();
        }
    }
    else{
        /// we have small amount of unique colors
        
    
        for(auto i : p2){
            move_inside(i);
            in[i] = true;
            //p2(1,i)
            
                //assert(x == 2);
                bool ok =false;
                p(i)
                for(j=0;j<n;j++){
                    if(!in[j])continue;
                    move_outside(j);
                    in[j] = false;
                    p2(2,j)
                    int x = press_button();
                    if(x == 1){
                        arr[i] = arr[j];
                        s.insert(arr[i]);
                        ok = true;
                        break;
                    }
                    p2(1,j)
                    move_inside(j);
                    in[j] = true;
                }
                assert(ok);
            
        }
        int ret = n;
        for(auto x : s){
            ret = min(ret,(int)s.count(x));
        }
        return ret; 

    }


}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:60:9: warning: unused variable 'sq' [-Wunused-variable]
   60 |     int sq = sqrt(n);
      |         ^~

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