Submission #1246961

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

sphinx

#include "sphinx.h"

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>
#define vp vector<pp>

vector<int> small(int n, std::vector<int> x, std::vector<int> y){
	vector<int> ans(n);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			vector<int> query(n, j);
			query[i] = -1;
			ll x = perform_experiment(query);
			if(x == 1){
				ans[i] = j;
				break;
			}
		}
	}
	return ans;
}

vector<int> find_colours(int n, std::vector<int> x, std::vector<int> y) {
	if(n <= 50) return small(n, x, y);
	vector<int> ans(n);
	for(int i = 0; i < n; i++){
		ll l = 0, r = n;
		while(l < r - 1){
			vector<int> query(n, n);
			query[i] = -1;
			ll s = (l + r)/2;
			ll ind = l;
			for(int j = 0; j < n; j++){
				if(i == j) continue;
				query[j] = ind;
				ind++;
				if(ind == s) break;
			}
			ll x = perform_experiment(query);
			if(x == s - l + 1) r = s;
			else l = s;
		}
		ans[i] = l;
	}
	return ans;

}

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