Submission #150876

#	Time	Username	Problem	Language	Result	Execution time	Memory
150876		percywtc	On the Grid (FXCUP4_grid)	C++17	43 / 100	65 ms	504 KiB

grid

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

vector<int> L, ub;

const int TRIALS = 1;

bool check(int N, int target_stick, int target_level, vector<int> undetermined, vector<int>& determined) {
	for (int t = 0; t < TRIALS; t++) {
		vector<int> p(1, target_stick);
		random_shuffle(undetermined.begin(), undetermined.end());

		for (int elm : undetermined) {
			if (elm != target_stick) {
				p.push_back(elm);
			}
		}
		for (int elm : determined) {
			p.push_back(elm);
		}

		int verdict = PutDisks(p);

		int cnt = N - (verdict - N + 1) + 1;

		for (int i = 0; i < cnt; i++) {
			int guess = i + N - cnt + 1;
			ub[p[i]] = min(ub[p[i]], guess);
		}
		
		if (verdict < target_level + N - 1) {
			return false;
		}
	}

	return true;
}

bool cmp(int u, int v) {
	return L[u] < L[v];
}

vector<int> SortDisks(int N) {
	L = vector<int>(N, 0);
	ub = vector<int>(N, N);

	srand(689);

	for (int i = N; i >= 1; i--) {
		vector<int> determined, undetermined;
		for (int j = 0; j < N; j++) {
			if (L[j]) {
				determined.push_back(j);
			} else {
				undetermined.push_back(j);
			}
		}

		int only = -1;
		for (int elm : undetermined) {
			if (ub[elm] >= i) {
				if (only == -1) {
					only = elm;
				} else {
					only = -2;
				}
			}
		}

		if (only > 0) {
			L[only] = i;
			continue;
		}

		sort(determined.begin(), determined.end(), cmp);

		random_shuffle(undetermined.begin(), undetermined.end());
		for (int elm : undetermined) {
			if (ub[elm] < i) {
				continue;
			}
			if (check(N, elm, i, undetermined, determined)) {
				L[elm] = i;
				break;
			}
		}
	}

	return L;
}

• Subtask 1: 12 / 12
• Subtask 2: 31 / 31
• Subtask 3: 0 / 57