Submission #1042748

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1042748	2024-08-03T10:25:47 Z	Nurislam	Rarest Insects (IOI22_insects)	C++17	0 / 100	32 ms	608 KB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()

template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}
int min_cardinality(int n) {
	vector<int> v;
	int k = 0;
	for(int i = 0; i < n; i++){
		move_inside(i);
		if(press_button() == 1){
			k++;
		}else {
			move_outside(i);
			v.pb(i);
		}
	}
	//~ for(auto i:v)cout << i << ' ';
	//~ cout << '\n';
	int l = 2, r = n/k, ans = 1;
	int cnt = k;
	while(l <= r){
		int m = (l+r)>>1;
		vector<int> up, dn;
		
		for(int i:v){
			move_inside(i);
			if(press_button() <= m){
				dn.pb(i);
			}else{
				up.pb(i);
				move_outside(i);
			}
		}
		
		if(k*m == (int)dn.size() + cnt){
			ans = m;
			l = m+1;
			v = up;
			cnt += dn.size();
		}else{
			r = m-1;
			v = dn;
		}
		
	}
	return ans;
}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	2 ms	344 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	3 ms	344 KB	Output is correct
9	Incorrect	4 ms	344 KB	Wrong answer.
10	Halted	0 ms	0 KB	-

Subtask #2

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	2 ms	344 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	3 ms	344 KB	Output is correct
9	Incorrect	4 ms	344 KB	Wrong answer.
10	Halted	0 ms	0 KB	-

Subtask #3

0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	29 ms	604 KB	Output is correct
8	Correct	9 ms	344 KB	Output is correct
9	Correct	32 ms	440 KB	Output is correct
10	Correct	21 ms	444 KB	Output is correct
11	Correct	15 ms	344 KB	Output is correct
12	Correct	14 ms	600 KB	Output is correct
13	Incorrect	24 ms	608 KB	Wrong answer.
14	Halted	0 ms	0 KB	-