Submission #737231

#	Time	Username	Problem	Language	Result	Execution time	Memory
737231		minhcool	Rarest Insects (IOI22_insects)	C++17	48.14 / 100	149 ms	664 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 min_cardinality(int n){
	vc.pb(0);
	moveinside(0);
	for(int i = 1; i < n; i++){
		moveinside(i);
		int temp = press_button();
		if(temp >= 2){
			moveoutside(i);
			vc2.pb(i);
		}
		else vc.pb(i);
	}
	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(int i = 0; i <= 12; i++){
		if(!queries[i].size()) break;
		sort(queries[i].begin(), queries[i].end(), cmp);
		for(auto it : vc) moveoutside(it);
		int lst = -1;
		for(auto it : queries[i]){
			int mid = (it.fi.fi + it.fi.se) / 2;
			while(lst < mid){
				lst++;
				moveinside(vc[lst]);
			}
			if(it.fi.fi == it.fi.se){
				cnt[it.fi.fi]++;
				continue;
			}
			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;
}

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:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i = 0; i < vc.size(); i++) cnt[i] = 1;
      |                 ~~^~~~~~~~~~~
insects.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i = 0; i < vc2.size(); i++) queries[0].pb({{0, vc.size() - 1}, vc2[i]});
      |                 ~~^~~~~~~~~~~~
insects.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i = 0; i < vc.size(); i++) mn = min(mn, cnt[i]);
      |                 ~~^~~~~~~~~~~

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