Submission #1144104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144104		Gr1sen	Sphinx's Riddle (IOI24_sphinx)	C++20	24 / 100	31 ms	656 KiB

sphinx

#include "sphinx.h"
#include<iostream>
#include<vector>

using namespace std;

#define vi vector<int>

int n;

void Lprint(vi &L) {
	cerr << "{";
	for (auto i : L) cerr << i << ", ";
	cerr << "}";
}

bool oink(int a, int p) {
	vi Q(n, 0);
	Q[p] = -1;
	int b = a;
	for (int i = 0; i < n; i++) {
		if (i == p) continue;
		Q[i] = b--;
		if (b < 0) break;
	}
	int c = perform_experiment(Q);
	//cerr << "perform_experiment(";
	//Lprint(Q);
	//cerr << ") : " << c << endl;
	return c == a+1;
}

vi find_colours(int N, vi X, vi Y) {
	n = N;
	vi Ans(n, -1);

	for (int i = 0; i < n; i++) {
		int l = 0, r = n-1;
		while (l < r) {
			int m = (l+r)/2;
			if (oink(m, i)) {
				r = m;
				continue;
			}
			l = m+1;
			continue;
		}
		Ans[i] = l;
	}
	return Ans;
}

/*
4 6
0 0 1 2    
0 1
0 2
0 3
1 2
1 3
2 3
4 8
*/

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 0 / 7
• Subtask 3: 0 / 33
• Subtask 4: 21 / 21
• Subtask 5: 0 / 36