oj.uz

Submission #965597

# Submission time Handle Problem Language Result Execution time Memory
965597 2024-04-19T02:21:30 Z IBory Cave (IOI13_cave) C++17
0 / 100
 166 ms 600 KB 
#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX = 5005;
int C[MAX], S[MAX], D[MAX], ID[MAX];

void exploreCave(int N) {
	for (int n = 0; n < N; ++n) {
		memset(C, 0x3f, sizeof(C));
		vector<int> cand;
		for (int p = 0; p < n; ++p) C[D[p]] = S[D[p]];
		for (int i = 0; i < N; ++i) {
			if (1e9 < C[i]) {
				cand.push_back(i);
				C[i] = 0;
			}
		}
		
		int init = tryCombination(C) != n;
		if (cand.size() == 1) {
			D[n] = cand[0];
			S[D[n]] = !init;
			break;
		}

		int l = -1, r = cand.size() - 1;
		while (l + 1 < r) {
			int mid = (l + r) >> 1;
			for (int i = 0; i <= mid; ++i) C[cand[i]] = 1;

			int go = tryCombination(C) != n;
			(init == go ? l : r) = mid;

			for (int i = 0; i <= mid; ++i) C[cand[i]] = 0;
		}

		D[n] = cand[r];
		ID[cand[r]] = n;
		S[D[n]] = !init;
	}

	answer(S, ID);
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 596 KB Answer is wrong
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 600 KB Answer is wrong
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Answer is wrong
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Answer is wrong
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 596 KB Answer is wrong
2 Halted 0 ms 0 KB -