Submission #1201242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201242		ansori	Sphinx's Riddle (IOI24_sphinx)	C++20	10 / 100	32 ms	1176 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);
//47.5 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);
	bool ok = true;
	for(int i = 0;i < m; ++ i){
		g[x[i]].push_back(y[i]);
		g[y[i]].push_back(x[i]);
		if(x[i] != i or y[i] != i + 1) ok = false;
	}
	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(ok){
		int c = 0;
		for(int i = 0;i < n; ++ i){
			G[i] = c;
			for(int j = i + 1;j < n; ++ j){
				vector<int> qu(n , n);
				for(int z = i;z <= j; ++ z) qu[z] = -1;
				if(perform_experiment(qu) == 1 + (i != 0) + (j != (n - 1))){
					i = j;
					G[j] = c;
				}
				else break;
			}
			cout << i << '\n';
			c ++;
		}
		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