oj.uz

Submission #1060121

# Submission time Handle Problem Language Result Execution time Memory
1060121 2024-08-15T10:45:20 Z AmirAli_H1 Rarest Insects (IOI22_insects) C++17
0 / 100
 35 ms 1624 KB 
// In the name of Allah

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

typedef		long long			ll;
typedef		pair<int, int>		pii;
typedef		pair<ll, ll>		pll;

#define		endl				'\n'
#define		sep					' '
#define		F					first
#define		S					second
#define		Mp					make_pair
#define		pb					push_back
#define		all(x)				(x).begin(),(x).end()
#define		len(x)				((ll) (x).size())

const int maxn = 2000 + 4;

int n, k, sz, res;
set<int> st; vector<int> ls;
int M[maxn], Mx[maxn];

void addx(int j) {
	st.insert(j); move_inside(j);
}

void delx(int j) {
	st.erase(j); move_outside(j);
}

int askx() {
	return press_button();
}

void del_all() {
	while (!st.empty()) {
		int j = *st.begin();
		delx(j);
	}
}

void cal_sz() {
	sz = 0;
	for (int i = 0; i < n; i++) {
		if (!M[i]) sz++;
	}
}

void checkx(ll R) {
	del_all();
	fill(Mx, Mx + n, 0); int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (M[i]) continue;
		addx(i);
		if (askx() > R) delx(i);
		else {
			Mx[i] = 1; cnt++;
		}
	}
	if (cnt == k * R) {
		res += R;
		for (int i = 0; i < n; i++) {
			if (M[i]) continue;
			if (Mx[i]) M[i] = 1;
		}
	}
	else {
		del_all();
		for (int i = n - 1; i >= 0; i--) {
			if (M[i]) continue;
			if (!Mx[i]) {
				M[i] = 1;
				addx(i);
				if (askx() > 1) delx(i);
			}
		}
		for (int i = n - 1; i >= 0; i--) {
			if (M[i]) continue;
			addx(i);
			if (askx() > 1) M[i] = 1;
			delx(i);
		}
	}
	
	cal_sz();
}

int min_cardinality(int N) {
	n = N; sz = n;
	
	for (int i = 0; i < n; i++) {
		addx(i);
		if (askx() > 1) delx(i);
	}
	for (int j : st) {
		ls.pb(j); M[j] = 1;
	}
	k = len(ls);
	
	res += 1; cal_sz();
	while (sz >= k) {
		int h = (sz / k);
		checkx((h + 1) / 2);
	}
	
	return res;
}

Subtask #1
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 3 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 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 3 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 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 0 ms 344 KB Output is correct
7 Correct 27 ms 448 KB Output is correct
8 Correct 11 ms 1624 KB Output is correct
9 Correct 27 ms 676 KB Output is correct
10 Partially correct 35 ms 464 KB Output is partially correct
11 Correct 26 ms 688 KB Output is correct
12 Correct 24 ms 344 KB Output is correct
13 Incorrect 33 ms 440 KB Wrong answer.
14 Halted 0 ms 0 KB -