oj.uz

Submission #903992

# Submission time Handle Problem Language Result Execution time Memory
903992 2024-01-11T16:15:21 Z Itamar Coreputer (IOI23_coreputer) C++17
60 / 100
 1 ms 600 KB 
#include "coreputer.h"
#include <vector>
using namespace std;
#define vi vector<int>
#include <algorithm>
#include <map>
map<vi, int> m;
int run_diagnostici(vi v) {
	if (m[v])return m[v] - 2;
	m[v] = 2+run_diagnostic(v);
	return m[v] - 2;
}
std::vector<int> malfunctioning_cores(int N) {
	vi ans(N);
	int l = 0, r = N-1;
	vi q;
	while (q.size()<5) {
		int mid = (l + r) / 2;
		vi v;
		for (int i = 0; i <= mid; i++)v.push_back(i);
		int a = run_diagnostici(v);
		q.push_back(a);
		if (a == 0) { l = mid, r = mid; }
		if (a == -1)l = mid+1;
		else r = mid;
	}
	int t = q.back(); int f = N - 1;
	if (l == N - 1) { for (int i = 0; i < N; i++)ans[i] = 0; ans[N - 1] = 1; return ans; }
	if (N>3&& l == N - 2) {
		if (t == 0) { ans[N - 2] = 1; ans[N - 1] = 1; return ans; }
		else if (t == -1) {
			ans[N - 1] = 1; return ans;
		}
		else {
			ans[N - 2] = 1;
		}
		f--;
		vi v; for (int i = 0; i < N; i++)if (i != N - 2)v.push_back(i);
		if (run_diagnostic(v) == 0)return v;
		int li = 0, ri = N - 3;
		ans[N - 1] = 1;
		while (li < ri) {
			int mid = (li + ri) / 2;
			vi vec; for (int i = 0; i <= mid; i++)vec.push_back(i); vec.push_back(N - 1);
			if (run_diagnostic(vec))ri = mid; else li = mid + 1;
		}
		ans[li] = 1;
		return ans;
	}
	int g=-1;
	int tt=t;

	for (int i = 0; i < f; i++) {
		vi v; for (int j = 0; j <= l; j++)if (i != j && (g!=j || i<=l))v.push_back(j);
		int a;
		if (i > l) {
			v.push_back(i);
			a = run_diagnostici(v);
			ans[i] = (tt < a);
		}
		else {
			a = run_diagnostici(v);
			ans[i] = (t > a);
			if (ans[i] && t!=0) {
				g = i; tt = a;
			}
		}
	}
	int x1=0;
	for (int i = 0; i < N - 1; i++) {
		if (ans[i] && i <= l)x1++;
		else if (ans[i])x1--;
	}
	ans[N - 1] = (x1 > (t));
	return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 356 KB Output is correct
3 Correct 0 ms 344 KB Output is correct

Subtask #2
40.0 / 40.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 1 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 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 1 ms 600 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 0 ms 344 KB Output is correct
27 Correct 1 ms 352 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 1 ms 356 KB Output is correct
37 Correct 0 ms 344 KB Output is correct
38 Correct 0 ms 344 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 356 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 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 1 ms 352 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 0 ms 344 KB Output is correct
37 Correct 0 ms 344 KB Output is correct
38 Correct 0 ms 344 KB Output is correct
39 Correct 1 ms 356 KB Output is correct
40 Correct 0 ms 344 KB Output is correct
41 Correct 0 ms 344 KB Output is correct
42 Incorrect 1 ms 344 KB Incorrect
43 Halted 0 ms 0 KB -