oj.uz

Submission #1060005

# Submission time Handle Problem Language Result Execution time Memory
1060005 2024-08-15T10:00:41 Z AmirAli_H1 Rarest Insects (IOI22_insects) C++17
0 / 100
 68 ms 1108 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;
set<int> st; int res;
vector<int> ls; int cnt[maxn];
int M[maxn], val[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);
	}
}

bool checkx(ll x) {
	del_all();
	for (int i = 0; i < n; i++) {
		addx(i);
		if (askx() > x) delx(i);
	}
	return (len(st) == k * x);
}

int solve1(int R) {
	int l = 1, r = R + 1;
	while (r - l > 1) {
		int mid = (l + r) / 2;
		if (checkx(mid)) l = mid;
		else r = mid;
	}
	return l;
}

int solve2(int R) {
	for (int j = __lg(R); j >= 0; j--) {
		del_all();
		for (int i = 0; i < k; i++) {
			if (i & (1 << j)) addx(ls[j]);
		}
		for (int i = 0; i < n; i++) {
			if (M[i]) continue;
			addx(i);
			if (askx() == 2) val[i] += (1 << j);
			delx(i);
		}
	}
	for (int i = 0; i < n; i++) cnt[val[i]]++;
	
	int mn = n;
	for (int i = 0; i < n; i++) mn = min(mn, cnt[val[i]]);
	return mn;
}

int min_cardinality(int N) {
	n = N;
	
	for (int i = 0; i < n; i++) {
		addx(i);
		if (askx() >= 2) delx(i);
	}
	for (int j : st) ls.pb(j);
	k = len(ls);
	
	for (int j = 0; j < k; j++) {
		val[ls[j]] = j; M[ls[j]] = 1;
	}
	
	del_all();
	if ((n / k) <= k) return solve1(n / k);
	else return solve2(k);
}

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 2 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 5 ms 596 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Incorrect 6 ms 444 KB Wrong answer.
13 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 2 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 5 ms 596 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Incorrect 6 ms 444 KB Wrong answer.
13 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 1 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 17 ms 440 KB Output is correct
8 Correct 15 ms 1108 KB Output is correct
9 Incorrect 68 ms 448 KB Wrong answer.
10 Halted 0 ms 0 KB -