oj.uz

Submission #28571

# Submission time Handle Problem Language Result Execution time Memory
28571 2017-07-16T07:31:27 Z Official Fan of ACG(#1221, cseteram, 16silver, pps789) 1-Color Coloring (FXCUP2_coloring) C++14
1 / 1
 0 ms 1940 KB 
#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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1940 KB Output is correct
2 Correct 0 ms 1940 KB Output is correct
3 Correct 0 ms 1940 KB Output is correct
4 Correct 0 ms 1940 KB Output is correct
5 Correct 0 ms 1940 KB Output is correct
6 Correct 0 ms 1940 KB Output is correct
7 Correct 0 ms 1940 KB Output is correct
8 Correct 0 ms 1940 KB Output is correct
9 Correct 0 ms 1940 KB Output is correct
10 Correct 0 ms 1940 KB Output is correct
11 Correct 0 ms 1940 KB Output is correct
12 Correct 0 ms 1940 KB Output is correct
13 Correct 0 ms 1940 KB Output is correct
14 Correct 0 ms 1940 KB Output is correct
15 Correct 0 ms 1940 KB Output is correct
16 Correct 0 ms 1940 KB Output is correct
17 Correct 0 ms 1940 KB Output is correct
18 Correct 0 ms 1940 KB Output is correct
19 Correct 0 ms 1940 KB Output is correct
20 Correct 0 ms 1940 KB Output is correct
21 Correct 0 ms 1940 KB Output is correct
22 Correct 0 ms 1940 KB Output is correct
23 Correct 0 ms 1940 KB Output is correct
24 Correct 0 ms 1940 KB Output is correct
25 Correct 0 ms 1940 KB Output is correct