Submission #1239619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239619		hengliao	Sphinx's Riddle (IOI24_sphinx)	C++20	36 / 100	36 ms	464 KiB

sphinx

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

#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back

typedef int ll;

namespace{
	
	const ll mxN=255;

	ll n, m;
	vll adj[mxN];
	bool visited[mxN];

	void dfs(ll cur, ll u, ll v){
		if(cur==u || cur==v || visited[cur]) return;
		visited[cur]=1;
		for(auto &it:adj[cur]){
			dfs(it, u, v);
		}
	}

	ll f(ll u, ll v){
		memset(visited, 0, sizeof(visited));
		ll cnt=0;
		for(ll i=0;i<n;i++){
			if(i==u || i==v) continue;
			if(!visited[i]){
				dfs(i, u, v);
				cnt++;
			}
		}
		return cnt;
	}

	ll ceil_div(ll a, ll b){
		return (a+b-1)/b;
	}
	
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y){
	n=N;
	m=X.size();
	for(ll i=0;i<m;i++){
		adj[X[i]].pb(Y[i]);
		adj[Y[i]].pb(X[i]);
	}
	vll ans(n, -1);

	auto qry=[&](ll c, ll tar){
		if(tar%2==0){
			vll tep(n, n);
			for(ll i=1;i<n;i+=2){
				tep[i]=c;
			}
			for(ll i=0;i<n;i+=2){
				if(i>tar) break;
				if(ans[i]!=-1) continue;
				tep[i]=-1;
			}
			if(perform_experiment(tep)<n){
				return true;
			}
			return false;
		}
		else{
			vll tep(n, n);
			for(ll i=0;i<n;i+=2){
				tep[i]=c;
			}
			for(ll i=1;i<n;i+=2){
				if(i>tar) break;
				if(ans[i]!=-1) continue;
				tep[i]=-1;
			}
			if(perform_experiment(tep)<n){
				return true;
			}
			return false;
		}
	};

	for(ll c=0;c<n;c++){
		for(ll i=0;i<2;i++){
			if(i==0){
				while(true){
					ll lef=0, rig=ceil_div(n, 2)-1;
					if(!qry(c, rig*2)){
						break;
					}
					ll good=-1;
					while(lef<=rig){
						ll mid=(lef+rig)/2;
						if(qry(c, 2*mid)){
							good=mid;
							rig=mid-1;
						}
						else{
							lef=mid+1;
						}
					}
					ans[good*2]=c;
				}
			}
			else{
				while(true){
					ll lef=0, rig=n/2-1;
					if(!qry(c, rig*2+1)){
						break;
					}
					ll good=-1;
					while(lef<=rig){
						ll mid=(lef+rig)/2;
						if(qry(c, 2*mid+1)){
							good=mid;
							rig=mid-1;
						}
						else{
							lef=mid+1;
						}
					}
					ans[good*2+1]=c;
				}
			}
		}
	}

	// cout<<qry(1, 0)<<'\n';

	return ans;
}

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