oj.uz

Submission #965280

# Submission time Handle Problem Language Result Execution time Memory
965280 2024-04-18T09:22:56 Z IBory Cave (IOI13_cave) C++17
0 / 100
 175 ms 860 KB 
#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

int tryCombination(int S[]);
void answer(int S[], int D[]);

const int MAX = 5005;
int C[MAX], S[MAX], D[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[p] = S[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[n] = (init == n);
			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] = r;
		S[n] = !init;
	}
	answer(S, D);
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 175 ms 860 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 344 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 344 KB Answer is wrong
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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