Submission #1247066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247066		ErJ	Sphinx's Riddle (IOI24_sphinx)	C++20	64 / 100	38 ms	912 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> complete(int n, vector<int> x, vector<int> 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;
}

vector<int> sedL(ll n, ll l, ll r, ll c){
	vector<int> ans(n, n);
	for(int i = l; i < r; i++){
		if(i % 2 == 1){
			ans[i] = c;
		}else{
			ans[i] = -1;
		}
	}
	return ans;
}

vector<int> sedS(ll n, ll l, ll r, ll c){
	vector<int> ans(n, n);
	for(int i = l; i < r; i++){
		if(i % 2 == 0){
			ans[i] = c;
		}else{
			ans[i] = -1;
		}
	}
	return ans;
}

vector<int> find_colours(int n, std::vector<int> x, std::vector<int> y) {
	if(n <= 50) return small(n, x, y);
	if(x.size() == n*(n - 1) / 2) return complete(n, x, y);
	vector<int> ans(n);
	for(int i = 0; i < n; i++){
		ll beg = 0;
		while(true){
			ll l = beg, r = n;
			if(l >= r) break;
			bool spec = false;
			if(l == n - 1) {
				l--;
				spec = true;
			}

			vector<int> query = sedL(n, l, r, i);
			
			ll x = perform_experiment(query);
			ll expected = r - l + 2;
			
			if(l == 0) expected--;
			if(r == n) expected--;

			if(expected != x){
				while(r - l > 2){
					ll s = (l + r) / 2;
					if(s % 2 == 1) s++;
					query = sedL(n, l, s, i);
					x = perform_experiment(query);
					expected = s - l + 2;
					
					if(l == 0) expected--;
					if(s == n) expected--;
					if(x == expected) l = s;
					else r = s;

					if(l % 2 == 1) l++;
					if(r % 2 == 0) r--;
					
				}
				if(spec) {
					ans[l + 1] = i;
					break;
				}
				ans[l] = i;
				beg = l + 2;
			}else{
				break;
			}
		}
		beg = 0;
		while(true){
			ll l = beg, r = n;
			if(l >= r) break;
			bool spec = false;
			if(l == n - 1) {
				l--;
				spec = true;
			}
			vector<int> query = sedS(n, l, r, i);
			ll x = perform_experiment(query);
			ll expected = r - l + 2;
			if(l == 0) expected--;
			if(r == n) expected--;
			if(expected != x){
				while(r - l > 2){
					
					ll s = (l + r) / 2;
					if(s % 2 == 0) s++;
					query = sedS(n, l, s, i);
					x = perform_experiment(query);

					expected = s - l + 2;
					if(l == 0) expected--;
					if(s == n) expected--;
					if(x == expected) l = s;
					else r = s;
					if(l % 2 == 0) l++;
					if(r % 2 == 1) r--;
				}
				if(spec) {
					ans[l + 1] = i;
					break;
				}
				ans[l] = i;
				beg = l + 2;
			}else{
				break;
			}
		}

		/*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: 33 / 33
• Subtask 4: 21 / 21
• Subtask 5: 0 / 36