Submission #737287

#	Time	Username	Problem	Language	Result	Execution time	Memory
737287		minhcool	Rarest Insects (IOI22_insects)	C++17	70 / 100	148 ms	504 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
vector<int> vc, vc2;
 
int cnt[N];
 
vector<iii> queries[13];
 
bool cmp(iii a, iii b){
	return (a.fi.fi + a.fi.se < b.fi.fi + b.fi.se);
}
 
bool in[N];
 
void moveinside(int u){
	if(in[u]) return;
	move_inside(u);
	in[u] = 1;
}
 
void moveoutside(int u){
	if(!in[u]) return;
	move_outside(u);
	in[u] = 0;
}
 
int p[N];
 
int mx[N], pref[N];
 
int min_cardinality(int n){
	for(int i = 0; i < n; i++) p[i] = i;
	shuffle(p, p + n, default_random_engine(7405));
	vc.pb(p[0]);
	moveinside(p[0]);
	for(int i = 1; i < n; i++){
		moveinside(p[i]);
		int temp = press_button();
		if(temp >= 2){
			moveoutside(p[i]);
			mx[p[i]] = vc.size();
			vc2.pb(p[i]);
		}
		else vc.pb(p[i]);
	}
	if(vc.size() <= 32){
		for(int i = 0; i < vc.size(); i++) cnt[i] = 1;
		for(int i = 0; i < vc2.size(); i++) queries[0].pb({{0, vc.size() - 1}, vc2[i]});
		for(auto it : vc) moveoutside(it);
	    int lst = vc.size() - 1;
		for(int i = 0; i <= 12; i++){
			if(!queries[i].size()) break;
   		   	sort(queries[i].begin(), queries[i].end(), cmp);
        	if((i & 1)){
        		//cout << i << "\n";
				//for(auto it : vc) assert(!in[it]);
				for(auto it : queries[i]){
					int mid = (it.fi.fi + it.fi.se) / 2;
					if(it.fi.fi == it.fi.se){
						cnt[it.fi.fi]++;
						continue;
					}
					for(int temp = it.fi.fi; temp <= mid; temp++) moveinside(vc[temp]);
					for(int temp = mid + 1; temp <= it.fi.se; temp++) moveoutside(vc[temp]);
					/*
    	            while(lst > mid){
    	            	moveoutside(vc[lst]);
    	                lst--;
    	            }
					while(lst < mid){
						lst++;
						moveinside(vc[lst]);
					}*/
					moveinside(it.se);
					if(press_button() >= 2) queries[i + 1].pb({{it.fi.fi, mid}, it.se});
					else queries[i + 1].pb({{mid + 1, it.fi.se}, it.se});
					moveoutside(it.se);
				}
   	    	}
   	 		else{
	    		//for(auto it : vc) if(!in[it]) cout << i << "\n";
	    		reverse(queries[i].begin(), queries[i].end());
	    		for(auto it : queries[i]){
					int mid = (it.fi.fi + it.fi.se) / 2;
					//assert(lst >= mid);
					if(it.fi.fi == it.fi.se){
						cnt[it.fi.fi]++;
						continue;
					}
					for(int temp = it.fi.fi; temp <= mid; temp++) moveinside(vc[temp]);
					for(int temp = mid + 1; temp <= it.fi.se; temp++) moveoutside(vc[temp]);
					moveinside(it.se);
					if(press_button() >= 2) queries[i + 1].pb({{it.fi.fi, mid}, it.se});
					else queries[i + 1].pb({{mid + 1, it.fi.se}, it.se});
					moveoutside(it.se);
				}
			}  
		}
		int mn = oo;
		for(int i = 0; i < vc.size(); i++) mn = min(mn, cnt[i]);
		return mn;
	}
	else{
		int l = 1, r = n / vc.size();
		while(l < r){
			int mid = (l + r + 1) >> 1;
			for(int i = 0; i < n; i++) moveoutside(i);
			for(int i = 0; i < n; i++){
				moveinside(i);			
				if(press_button() > mid) moveoutside(i);
			}
			int total = 0;
			for(int i = 0; i < n; i++) total += in[i];
			if(total == mid * vc.size()) l = mid;
			else r = mid - 1;
		}
		return l;
	}
}

Compilation message (stderr)

insects.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int i = 0; i < vc.size(); i++) cnt[i] = 1;
      |                  ~~^~~~~~~~~~~
insects.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i = 0; i < vc2.size(); i++) queries[0].pb({{0, vc.size() - 1}, vc2[i]});
      |                  ~~^~~~~~~~~~~~
insects.cpp:115:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |   for(int i = 0; i < vc.size(); i++) mn = min(mn, cnt[i]);
      |                  ~~^~~~~~~~~~~
insects.cpp:65:10: warning: unused variable 'lst' [-Wunused-variable]
   65 |      int lst = vc.size() - 1;
      |          ^~~
insects.cpp:129:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |    if(total == mid * vc.size()) l = mid;
      |       ~~~~~~^~~~~~~~~~~~~~~~~~

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