Submission #1201213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201213		ansori	스핑크스 (IOI24_sphinx)	C++20	10 / 100	31 ms	1172 KiB

sphinx

#include "sphinx.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int msz = 256;
int perform_experiment(vector<int> E);
//64 points
int n , m;
vector<int> G , g[msz] , col;
vector<bool> w;
void dfs(int v){
	w[v] = 1;
	for(auto to : g[v]){
		if((! w[to]) and col[to] == col[v]){
			dfs(to);
		}
	}
}
int expected(){
	w = vector<bool> (n , 0);
	int cmp = 0;
	for(int i = 0;i < n; ++ i){
		if(! w[i]){
			cmp ++;
			dfs(i);
		}
	}
	return cmp;
}
vector<int> find_colours(int N, std::vector<int> x, std::vector<int> y) {
	n = N , m = x.size();
	G = vector<int> (n , 0);
	for(int i = 0;i < m; ++ i){
		g[x[i]].push_back(y[i]);
		g[y[i]].push_back(x[i]);
	}
	if(n <= 52){
		col = vector<int> (n , n);
		for(int i = 0;i < n; ++ i){
			col[i] = -1;
			col[g[i][0]] = -1;
			int cmp = expected();
			for(int j = 0;j < n; ++ j){
				vector<int> qu(n , n);
				qu[i] = -1;
				qu[g[i][0]] = j;
				if(perform_experiment(qu) == cmp){
					G[i] = j;
					break;
				}
			}
			col[i] = n;
			col[g[i][0]] = n;
		}
		return G;
	}
	if(m == n * (n - 1) / 2){
	    for(int i = 0;i < n; ++ i){
	    	int l = 0;
	    	int r = n;
	    	while(l + 1 < r){
	    		int mid = (l + r) / 2;
	    		vector<int> qu(n , n);
	    		for(int j = 0;j < (r - mid); ++ j){
	    			qu[g[i][j]] = mid + j;
	    		}
	    		if(perform_experiment(qu) == (r - mid + 1)) l = mid;
	    		else r = mid;
	    	}
	    	G[i] = l;
	    }
		return G;
	}
	if(m == n - 1){
		for(int i = 0;i < n; ++ i){
	    	vector<int> qu(n , n);
			for(int j = 0;j < n; j += 2) qu[j] = -1;
			int cnt = perform_experiment(qu) , p = -1 , k = 0;
			for(int j = 0;j < cnt; ++ j){
				int l = p;
				int r = n / 2;
				while(l + 1 < r){
					int mid = (l + r) / 2;
					qu = vector<int> (n , n);
					for(int z = 0;z < mid; ++ z) qu[z * 2] = -1;
					if(perform_experiment(qu) - k > 0) r = mid;
					else l = mid; 
				}
				qu = vector<int> (n , n);
				p = r;
				for(int z = 0;z <= p; ++ z) qu[p * 2] = -1;
				k = perform_experiment(qu);
				G[p * 2] = i;
			}
			qu = vector<int> (n , n);
			for(int j = 1;j < n; j += 2) qu[j] = -1;
			cnt = perform_experiment(qu) , p = -1 , k = 0;
			for(int j = 0;j < cnt; ++ j){
				int l = p;
				int r = (n - 1) / 2;
				while(l + 1 < r){
					int mid = (l + r) / 2;
					qu = vector<int> (n , n);
					for(int z = 0;z < mid; ++ z) qu[z * 2 + 1] = -1;
					if(perform_experiment(qu) - k > 0) r = mid;
					else l = mid; 
				}
				qu = vector<int> (n , n);
				p = r;
				for(int z = 0;z <= p; ++ z) qu[z * 2 + 1] = -1;
				k = perform_experiment(qu);
				G[p * 2 + 1] = i;
			}
		}
		return G;
	}
	return G;
}

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