oj.uz

Submission #28537

# Submission time Handle Problem Language Result Execution time Memory
28537 2017-07-16T07:07:25 Z Official Fan of ACG(#1221, cseteram, 16silver, pps789) 1-Color Coloring (FXCUP2_coloring) C++14
0 / 1
 0 ms 1940 KB 
#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) {
		random_shuffle(cands.begin() + lo, cands.begin() + hi + 1);
		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 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())));
			cands.erase(cands.find(chain.back()));
		}
	}
}

Compilation message

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

Subtask #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 Incorrect 0 ms 1940 KB Output isn't correct
18 Halted 0 ms 0 KB -