QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#334938#8215. Isomorphic Delightucup-team1209#RE 0ms0kbC++203.2kb2024-02-22 15:21:092024-02-22 15:21:09

Judging History

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

  • [2024-02-22 15:21:09]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-02-22 15:21:09]
  • 提交

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;n;++i) {
			if(vecs[i].first <= n) {
				v.push_back(vecs[i].second);
				n -= vecs[i].first;
			} else {
				if(size[v[0]] < vecs[i].first) {
					for(int j = 0;j < (int) v.size();++j) {
						const int sub = vecs[i].first - size[v[j]];
						if(sub <= n) {
							n -= sub;
							v.erase(v.begin() + j);
							v.push_back(vecs[i].second);
							break;
						}
					}
				}
			}
		}
		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

*/

详细

Test #1:

score: 0
Runtime Error

input:

1

output:


result: