QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#334900#8215. Isomorphic Delightucup-team1209#WA 810ms136196kbC++202.9kb2024-02-22 15:01:482024-02-22 15:01:48

Judging History

你现在查看的是最新测评结果

  • [2024-02-22 15:01:48]
  • 评测
  • 测评结果:WA
  • 用时:810ms
  • 内存:136196kb
  • [2024-02-22 15:01:48]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin;
using std::cout;
using pr = std::pair<int, int>;
using u64 = unsigned long long;
const u64 C = 12894718241;
u64 f(u64 x) {
	x ^= x << 13;
	x ^= x >> 7;
	x ^= x << 17;
	return x;
}
std::vector<pr> edge;

const int N = 3000005;
std::vector<int> son[N];

void cyctree(int n, int base = 0) {
	for(int i = 2;i <= n - 3;++i) {
		edge.emplace_back(base + i, base + i - 1);
	}
	edge.emplace_back(base + 1, base + n - 3);
	edge.emplace_back(base + 1, base + n - 2);
	edge.emplace_back(base + 2, base + n - 1);
	edge.emplace_back(base + n - 1, base + n);
}
int tct;
int tree(int x) {
	int p = ++tct;
	for(int z : son[x]) {
		edge.emplace_back(p, tree(z));
	}
	return p;
}


u64 hash[N];
int size[N];
int ed[N];
int cc;
int n;

int okcc = 0;
std::map<std::vector<u64>, int> map;

void hashset(int x) {
	if(son[x].size() > 1) return ;
	std::vector<u64> hashs;
	auto dfs = [&](int x, u64 ancv, auto dfs) -> void {
		hashs.push_back(hash[x] + ancv);
		for(int i : son[x]) {
			dfs(i, f(hash[x] + ancv - f(hash[i])), dfs);
		}
	};
	dfs(x, 0, dfs);
	sort(hashs.begin(), hashs.end());
	for(int i = 1;i < (int) hashs.size();++i) {
		if(hashs[i] == hashs[i - 1]) {
			return ;
		}
	}
	okcc += hashs.size();
	map[hashs] = x;
}



int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	size[1] = 1, hash[1] = C, ed[1] = 1, cc = 1;
	hashset(1);
	const int M = 21;

	for(int i = 2;i <= M;++i) {
		std::vector<int> s;
		auto dfs = [&](int rem, int idx, auto & s, auto dfs) {
			if(rem == 0) {
				size[++cc] = i;
				hash[cc] += C;
				son[cc] = s;
				for(int x : s) {
					hash[cc] += f(hash[x]);
				}
				hashset(cc);
				return ;
			}
			idx = std::min(idx, ed[rem]);
			for(int i = idx;i >= 1;--i) {
				s.push_back(i);
				dfs(rem - size[i], i - 1, s, dfs);
				s.pop_back();
			}
		};
		dfs(i - 1, 1e9, s, dfs);
		ed[i] = cc;
	}
	std::vector<std::pair<int, int>> vecs;
	for(auto & [a, b] : map) {
		vecs.emplace_back(size[b], b);
	}

	sort(vecs.begin(), vecs.end());
	auto greedy = [&](int n) {
		std::vector<int> v;
		for(int i = 1;vecs[i].first <= n - 6 || vecs[i].first == n;++i) {
			v.push_back(vecs[i].second);
			n -= vecs[i].first;
		}
		return v;
	};
	std::vector<int> ans;
	for(int idx = 0;idx < 2;++idx) {
		std::vector<int> v;
	}
	cin >> n;
	auto A = greedy(n);
	if(n >= 7 || n == 1) {
		auto B = greedy(n - 1); B.push_back(1);
		if(B.size() > A.size()) {
			A = B;
		}
	}
	int cyc_size = n;
	for(int x : A) cyc_size -= size[x];
	if(cyc_size >= 6 || cyc_size == 0) {
		cout << "YES" << '\n';
		if(cyc_size) cyctree(tct = cyc_size);
		for(auto x : A) {
			tree(x);
		}
		cout << edge.size() << '\n';
		for(auto [a, b] : edge) {
			cout << a << ' ' << b << '\n';
		}
	} else {
		cout << "NO" << '\n';
	}
//	cin >> n;

}

/*
14
YES
12
2 1
3 2
1 3
1 4
2 5
5 6
11 12
10 11
9 10
9 13
8 9
7 8

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 776ms
memory: 134736kb

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

score: 0
Accepted
time: 785ms
memory: 136196kb

input:

6

output:

YES
6
2 1
3 2
1 3
1 4
2 5
5 6

result:

ok Everything ok

Test #3:

score: 0
Accepted
time: 781ms
memory: 134336kb

input:

4

output:

NO

result:

ok Everything ok

Test #4:

score: 0
Accepted
time: 795ms
memory: 133720kb

input:

2

output:

NO

result:

ok Everything ok

Test #5:

score: 0
Accepted
time: 800ms
memory: 135560kb

input:

3

output:

NO

result:

ok Everything ok

Test #6:

score: 0
Accepted
time: 810ms
memory: 134976kb

input:

5

output:

NO

result:

ok Everything ok

Test #7:

score: 0
Accepted
time: 798ms
memory: 136176kb

input:

7

output:

YES
6
5 6
4 5
3 4
3 7
2 3
1 2

result:

ok Everything ok

Test #8:

score: 0
Accepted
time: 754ms
memory: 134392kb

input:

8

output:

YES
6
5 6
4 5
3 4
3 7
2 3
1 2

result:

ok Everything ok

Test #9:

score: -100
Wrong Answer
time: 769ms
memory: 134188kb

input:

9

output:

YES
8
2 1
3 2
4 3
5 4
1 5
1 6
2 7
7 8

result:

wrong answer contestant's solution is worse (more edges) than jury's