제출 #150672

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
150672		Ian and 2-bit memory (#200)	On the Grid (FXCUP4_grid)	C++17	12 / 100	14 ms	384 KiB

grid

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

const int TRIALS = 5;

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);
		if (verdict < target_level + N - 1) {
			return false;
		}
	}

	return true;
}

vector<int> L;

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

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

	srand(882);

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

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

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

	return L;
}

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