Submission #28526

#	Time	Username	Problem	Language	Result	Execution time	Memory
28526		Official Fan of ACG (#68)	1-Color Coloring (FXCUP2_coloring)	C++14	0 / 1	0 ms	1940 KiB

coloring

#include "coloring.h"
#include<vector>
#include<algorithm>
#include<set>
using namespace std;

int colorCnt;

int find_back(int x, vector<int> cands) {
	random_shuffle(cands.begin(), cands.end());

	int lo = 0, hi = cands.size() - 1;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		// color lo...mid
		for (int i = lo; i <= mid; i++) Color(cands[i]), colorCnt++;
		int cnt = GetColor(x);
		if (!cnt) hi = mid;
		else lo = mid + 1;
	}
	return cands[lo];
}

void ColoringSame(int N){
	colorCnt = 0;
	vector<int> chain;
	set<int> cands;
	for (int i = 2; i <= N; i++) cands.insert(i);
	chain.push_back(find_back(1, vector<int>(cands.begin(), cands.end())));
	cands.erase(cands.find(chain.back()));

	while (1) {
		int X = chain.size();
		int left = 1 + (N - X - 1)*(N - X - 1) + X;
		if (colorCnt + left <= 7300) {
			Color(1);
			for (int c : cands) for (int c : cands) Color(c);
			reverse(chain.begin(), chain.end());
			for (int x : chain) Color(x);
			return;
		}
		else {
			chain.push_back(find_back(1, vector<int>(cands.begin(), cands.end())));
			cands.erase(cands.find(chain.back()));
		}
	}
}

Compilation message (stderr)

coloring.cpp: In function 'void ColoringSame(int)':
coloring.cpp:37:13: warning: unused variable 'c' [-Wunused-variable]
    for (int c : cands) for (int c : cands) Color(c);
             ^

• Subtask 1: 0 / 1