Submission #636550

#	Time	Username	Problem	Language	Result	Execution time	Memory
636550		MohamedAliSaidane	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	70 ms	572 KiB

insects

#include<bits/stdc++.h>
#include "insects.h"
#include <ext/pb_ds/assoc_container.hpp>
        using namespace __gnu_pbds;
        using namespace std;

        typedef tree<int,null_type,less<int>,rb_tree_tag,
        tree_order_statistics_node_update> indexed_set;

        typedef long long ll;
        typedef long double ld;

        //#define int ll

        typedef pair<int,int> pii;
        typedef pair<ll,ll> pll;
        typedef pair<ld,ld> pld;

        typedef vector<int> vi;
        typedef vector<ll> vll;
        typedef vector<pii> vpi;
        typedef vector<pll> vpl;

        #define pb push_back
        #define popb pop_back
        #define pp pop_back
        #define pf push_front
        #define popf pop_front
        #define all(x) (x).begin(),(x).end()
        #define ff first
        #define ss second



        int nx[8] = {0,0,1,-1, 1, 1, -1, -1}, ny[8] = {1,-1,0,0, 1, -1, 1, -1};
        ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
        ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}

        const ll MOD = 1e9 + 7;
        ll  mod(ll x, ll m = MOD){return (x + m)%m;}
        /*
        int press_button();
        void move_inside(int i );
        void move_outside(int i);
        */
        int min_cardinality(int n)
        {
            mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
            int T = 0;
            set<int> machine;
            for(int i = 0; i < n; i++)
            {
                move_inside(i);
                machine.insert(i);
                if(press_button() > 1)
                {
                    machine.erase(i);
                    move_outside(i);
                }
                else
                {
                    T++;
                }
            }
            if(T == n)
                return 1;
            if(T == 1)
                return n;
            set<int> vis;
            vis.insert(1); vis.insert(n);
            vi s[n + 1];
            for(auto e: machine)
                s[1].pb(e);
            for(int i = 0; i < n; i++)
                s[n].pb(i);
            int debut = 2;
            int fin = n/T;
            int rep = 1;
            while(debut <= fin)
            {
                int mid = (debut + fin)/2;
                int nxt = *(vis.lower_bound(mid));
                set<int> just_added ;
                int cnt = 0;
                for(auto e: s[nxt])
                {
                    if(machine.count(e) == 0)
                    {
                        move_inside(e);
                        machine.insert(e);
                        if(press_button() > mid)
                        {
                            move_outside(e);
                            machine.erase(e);
                        }
                        else
                        {
                            just_added.insert(e);
                            cnt++;
                        }
                    }
                    else
                        cnt++;
                }
                vis.insert(mid);
                for(auto e: machine)
                    s[mid].pb(e);
                shuffle(all(s[mid]), rng);
                if(cnt >= mid * T)
                {
                    rep = mid;
                    debut = mid + 1;
                }
                else
                {
                    fin = mid - 1;
                    for(auto e: just_added)
                        machine.erase(e), move_outside(e);
                }
            }
            return rep;
        }

/*
static inline constexpr int kMaxQueries = 40000;

static int N;
// Insect types are compressed to colors in the range [0, N).
static std::vector<int> color;
static std::vector<bool> in_box;

static std::vector<int> color_occurrences;
static std::multiset<int> max_occurrences;

static std::vector<int> op_counter(3, 0);

static inline void protocol_violation(std::string message) {
  printf("Protocol Violation: %s\n", message.c_str());
  exit(0);
}

void move_inside(int i) {
  if (i < 0 || i >= N) {
    protocol_violation("invalid parameter");
  }
  ++op_counter[0];
  if (op_counter[0] > kMaxQueries) {
    protocol_violation("too many calls");
  }
  if (!in_box[i]) {
    in_box[i] = true;
    max_occurrences.erase(max_occurrences.find(color_occurrences[color[i]]));
    ++color_occurrences[color[i]];
    max_occurrences.insert(color_occurrences[color[i]]);
  }
}

void move_outside(int i) {
  if (i < 0 || i >= N) {
    protocol_violation("invalid parameter");
  }
  ++op_counter[1];
  if (op_counter[1] > kMaxQueries) {
    protocol_violation("too many calls");
  }
  if (in_box[i]) {
    in_box[i] = false;
    max_occurrences.erase(max_occurrences.find(color_occurrences[color[i]]));
    --color_occurrences[color[i]];
    max_occurrences.insert(color_occurrences[color[i]]);
  }
}

int press_button() {
  ++op_counter[2];
  if (op_counter[2] > kMaxQueries) {
    protocol_violation("too many calls");
  }
  return *(max_occurrences.rbegin());
}

int main() {
  assert(1 == scanf("%d", &N));
  color.resize(N);
  in_box.assign(N, false);

  std::map<int, int> type_to_color;
  for (int i = 0; i < N; ++i) {
    int Ti;
    assert(1 == scanf("%d", &Ti));
    if (type_to_color.find(Ti) == type_to_color.end()) {
      int new_color = type_to_color.size();
      type_to_color[Ti] = new_color;
      max_occurrences.insert(0);
    }
    color[i] = type_to_color[Ti];
  }

  color_occurrences.assign(type_to_color.size(), 0);

  int answer = min_cardinality(N);
  int Q = *std::max_element(op_counter.begin(), op_counter.end());
  printf("%d\n", answer);
  printf("%d\n", Q);
  return 0;
}
/*
*/

Compilation message (stderr)

insects.cpp:207:1: warning: "/*" within comment [-Wcomment]
  207 | /*
      |

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