oj.uz

Submission #832987

# Submission time Handle Problem Language Result Execution time Memory
832987 2023-08-21T18:21:59 Z MeGustaElArroz23 Rarest Insects (IOI22_insects) C++17
0 / 100
 290 ms 208 KB 
#include "insects.h"

using namespace std;

#include<bits/stdc++.h>

#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
#define fi first
#define se second
#define pb push_back
#define vb vector<bool>

int n;
vb box;
vb basic_box;
int basic_box_size;

void create_basic_box(){
	basic_box=vb(n,0);
	for (int i=0;i<n;i++){
		move_inside(i);
		box[i]=1;
		if (press_button()>1){
			move_outside(i);
			box[i]=0;
		}
	}
	basic_box=box;
	basic_box_size=0;
	for (int x:basic_box) basic_box_size+=x;
}

void clear_box(){
	for (int i=0;i<n;i++){
		if (box[i] && (! basic_box[i])){
			box[i]=0;
			move_outside(i);
		}
	}
}

int check_ans(int m){
	for (int i=0;i<n;i++){
		move_inside(i);
		box[i]=1;
		if (press_button()>m){
			move_outside(i);
			box[i]=0;
		}
	}
	int count=0;
	for (int x:box) count+=x;
	if (count==m*basic_box_size){
		basic_box=box;
		return 1;
	}
	else return 0;
}

int min_cardinality(int N) {
	n=N;
	box=vb(n,0);
    create_basic_box();
	clear_box();

	if (basic_box_size==1) return N;

	int l=1;
	int r=n/basic_box_size+1;

	while (l!=r-1){
		int m=(5*l+3*r)/8;
		if (check_ans(m)) l=m;
		else r=m;
		clear_box();
	}

	return l;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 243 ms 208 KB Too many queries.
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 243 ms 208 KB Too many queries.
5 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 290 ms 208 KB Too many queries.
2 Halted 0 ms 0 KB -