Submission #1208272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208272		vidux	Sphinx's Riddle (IOI24_sphinx)	C++17	31 / 100	34 ms	660 KiB

sphinx

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

#define FOR(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n, m) for (int i = n; i <= m; ++i)
#define REPR(i, n, m) for (int i = n; i >= m; --i)
#define FORR(x, a) for (auto& x : a)
#define FORR2(x, y, a) for (auto& [x, y] : a)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(a) ((int)a.size())

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vb> vvb;

const int INF = 1e9;
const ll LLINF = 1e18;

#include "sphinx.h"

std::vector<int> find_colours(int n, std::vector<int> X, std::vector<int> Y) {
	vi ans(n);
	if (n <= 50) {
		FOR(i, n) {
			FOR(j, n) {
				vi e(n, j);
				e[i] = -1;
				int cnt = perform_experiment(e);
				if (cnt == 1) {
					ans[i] = j;
					break;
				}
			}
		} 
		return ans;
	}
	FOR(i, n) {
		//cout << "i:" << i << endl;
		int l = 0, r = n-1;
		while (l < r) {
			vi e(n, n);
			e[i] = -1;
			int m = (l+r)/2;
			int k = m-l+1;
			int added = 0;
			for (int j = 0; added < k; j++) {
				if (i == j) continue;
				e[j] = l+added++;
			}
			//cout << "\tl: " << l << " r: " << r << endl;
			//cout << "\te: "; FORR(x, e) cout << x << " "; cout << endl;
			int cnt = perform_experiment(e);
			int goodCnt = 1 + m-l+1;
			if (goodCnt == cnt) r = m;
			else l = m+1;
		}
		ans[i] = l;
	}
	return ans;
}

/*
5 10
1 2 3 1 0
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4
*/

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