Submission #28571

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

coloring

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

int colorCnt;

int find_back(int x, vector<int> cands, mt19937& g) {
	shuffle(cands.begin(), cands.end(), g);
	int st = colorCnt;
	int lo = 0, hi = cands.size() - 1;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		int L = mid - lo + 1, R = hi - mid;
		if (L > R) mid--;
		// 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;
	}
	int ed = colorCnt;
	return cands[lo];
}

void ColoringSame(int N){
	random_device rd;
	mt19937 g(rd());
	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()), g));
	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 d : 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(chain.back(), vector<int>(cands.begin(), cands.end()), g));
			cands.erase(cands.find(chain.back()));
		}
	}
}

Compilation message (stderr)

coloring.cpp: In function 'int find_back(int, std::vector<int>, std::mt19937&)':
coloring.cpp:12:6: warning: unused variable 'st' [-Wunused-variable]
  int st = colorCnt;
      ^
coloring.cpp:24:6: warning: unused variable 'ed' [-Wunused-variable]
  int ed = colorCnt;
      ^
coloring.cpp: In function 'void ColoringSame(int)':
coloring.cpp:43:13: warning: unused variable 'd' [-Wunused-variable]
    for (int d : cands) for (int c : cands) Color(c);
             ^

• Subtask 1: 1 / 1