답안 #1042748

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1042748	2024-08-03T10:25:47 Z	Nurislam	드문 곤충 (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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-