oj.uz

Submission #1062782

# Submission time Handle Problem Language Result Execution time Memory
1062782 2024-08-17T10:46:10 Z Arapak Rarest Insects (IOI22_insects) C++17
10 / 100
 57 ms 592 KB 
#include "insects.h"
#include "bits/stdc++.h"

using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#ifdef DEBUG
auto& operator<<(auto& os, pair<auto, auto> &p) {
	return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto& os, const auto &v) {
	os<<"{";
	for(auto it=begin(v);it!=end(v);++it) {
		if(it != begin(v)) os<<", ";
		os<<(*it);
	}
	return os<<"}";
}

void dbg_out(auto... x) {
	((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif

int n;
vi perm;
vector<bool> added;

void in(int i) {
	if(added[i]) return;
	added[i] = true;
	move_inside(perm[i]);
}
void out(int i) {
	if(!added[i]) return;
	added[i] = false;
	move_outside(perm[i]);
}

vi siz;
vi ind;

void find(int index) {
	dbg(index);
	in(index);
	for(auto x : ind)
		in(x);
	if(press_button() == 1) {
		siz[index] = 1;
		ind.push_back(index);
		return;
	}
	int b = 0, e = sz(ind)-1;
	while(b < e) {
		int mid = (b + e + 1) / 2;
		rep(i,b,mid) in(ind[i]); 
		rep(i,mid,e+1) out(ind[i]);
		dbg(b, e, mid);
		if(press_button() == 1)
			b = mid;
		else
			e = mid - 1;
	}
	dbg(ind[b]);
	siz[ind[b]]++;
	out(index);
}

int min_cardinality(int N) {
	n = N;
	perm.resize(n);
	iota(all(perm), 0);
	random_shuffle(all(perm));
	added.assign(n, 0);
	siz.assign(n, -1);
	siz[0] = 1;
	ind.push_back(0);
	rep(i,1,n) find(i);
	dbg(siz);
	dbg(ind);
	int mini = n;
	rep(i,0,n)
		if(siz[i] != -1)
			mini = min(mini, siz[i]);
	return mini;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 6 ms 344 KB Output is correct
9 Correct 4 ms 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 4 ms 344 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Correct 4 ms 344 KB Output is correct
14 Correct 4 ms 344 KB Output is correct
15 Correct 5 ms 344 KB Output is correct
16 Correct 3 ms 344 KB Output is correct
17 Correct 6 ms 344 KB Output is correct
18 Correct 4 ms 344 KB Output is correct
19 Correct 5 ms 344 KB Output is correct
20 Correct 6 ms 344 KB Output is correct
21 Correct 5 ms 344 KB Output is correct
22 Correct 4 ms 344 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 6 ms 344 KB Output is correct
9 Correct 4 ms 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 4 ms 344 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Correct 4 ms 344 KB Output is correct
14 Correct 4 ms 344 KB Output is correct
15 Correct 5 ms 344 KB Output is correct
16 Correct 3 ms 344 KB Output is correct
17 Correct 6 ms 344 KB Output is correct
18 Correct 4 ms 344 KB Output is correct
19 Correct 5 ms 344 KB Output is correct
20 Correct 6 ms 344 KB Output is correct
21 Correct 5 ms 344 KB Output is correct
22 Correct 4 ms 344 KB Output is correct
23 Correct 4 ms 344 KB Output is correct
24 Correct 6 ms 444 KB Output is correct
25 Correct 51 ms 344 KB Output is correct
26 Correct 39 ms 344 KB Output is correct
27 Correct 4 ms 344 KB Output is correct
28 Incorrect 23 ms 592 KB Too many queries.
29 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 9 ms 344 KB Output is correct
8 Correct 12 ms 460 KB Output is correct
9 Incorrect 57 ms 344 KB Too many queries.
10 Halted 0 ms 0 KB -