QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#142375#5665. AA Country and King DreamoonThe_HallakRE 52ms206048kbC++172.3kb2023-08-19 00:49:292023-08-19 00:49:29

Judging History

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

  • [2023-08-19 00:49:29]
  • 评测
  • 测评结果:RE
  • 用时:52ms
  • 内存:206048kb
  • [2023-08-19 00:49:29]
  • 提交

answer

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const ll N = 3e5 + 10, MM = 1e9 + 7, MAX = 1e18;

int p[N];
set<ll>s, cant;
deque<ll>adj[N];

int solve() {

	int n; cin >> n;
	
	vector<ll>v;

	if (n == 0) {
		n = 3e5;
		v = vector<ll>(2*n-1, 0);
	}
	else {
		v.resize(2 * n - 1);
		for (auto& x : v) cin >> x;
	}
	
	

	for (int i = 1; i <= n; i++) {
		s.insert(i);
	}
	if(v.back()!=0)
		for (int i = v.size() - 2; i >= 0 && v[i]; i--) {
			if (!p[v[i]]) {
				p[v[i]] = v[i + 1];
				adj[v[i + 1]].push_back(v[i]);
			}
			if (p[v[i + 1]] == v[i]) {
				s.erase(v[i + 1]);
			}
			cant.insert(v[i]);
		}

	v[0] = 1;
	p[1] = 100000000;
	s.erase(1);
	int i = 1;

	for (i = 1; (i < 2 * n - 1) && v[i]; i++) {
		if (!p[v[i]]) {
			p[v[i]] = v[i - 1];
		}
		else {
			s.erase(v[i - 1]);
		}
		s.erase(v[i]);
	}

	for (auto& x : adj) {
		sort(x.begin(), x.end());
	}

	for (; i < v.size() && !v[i];) {
		while (adj[v[i - 1]].size()) { 

			if (!s.count(adj[v[i - 1]].front())) adj[v[i - 1]].pop_front();

			else if (*s.begin() == adj[v[i - 1]].front()) {
				s.erase(s.begin());
				v[i] = adj[v[i - 1]].front();
				p[v[i]] = v[i - 1];
				i++;
				if (i == v.size())break;
				adj[v[i - 1]].pop_front();
			}
			else {
				v[i] = *s.begin();
				p[v[i]] = v[i - 1];
				i++;
				if (i == v.size())break;
				s.erase(s.begin());
			}
		}
		if (i == v.size())break;
		while (s.size() && *s.begin() < p[v[i - 1]]) {
			v[i] = *s.begin();
			p[v[i]] = v[i - 1];
			i++;
			if (i == v.size())break;
			s.erase(s.begin());
		}

		if (i == v.size())break;
		if (!cant.count(v[i - 1])) {
			v[i] = p[v[i - 1]];
			i++;
			if (i == v.size())break;
		}
		else {
			v[i] = *s.begin();
			s.erase(s.begin());
			p[v[i]] = v[i - 1];
			i++;
			if (i == v.size())break;
		}
	}

	for (auto x : v) cout << x << " ";
	cout << '\n';

	for (int i = 1; i <= min(N,2ll*n); i++) {
		p[i] = 0;
		adj[i].clear();
	}

	s.clear();
	cant.clear();
	return 0;
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int t = 1;
	cin >> t;
	int i = 1;
	while (t--) {
		//cout << "case " << i << ": ";
		solve();
	}

	return 0;
}
/*

5
0 2 3 2 0 2 1 5 1

*/

詳細信息

Test #1:

score: 100
Accepted
time: 52ms
memory: 206048kb

input:

9
5
1 2 3 2 0 2 1 5 1
5
1 2 3 0 0 2 1 5 1
5
1 2 0 0 0 2 1 5 1
5
1 2 0 0 0 0 1 5 1
5
1 0 0 0 0 0 1 5 1
5
1 0 0 0 0 0 0 5 1
5
1 0 0 0 0 0 0 0 1
5
1 0 0 0 0 0 0 0 0
5
0 0 0 0 0 0 0 0 0

output:

1 2 3 2 4 2 1 5 1 
1 2 3 2 4 2 1 5 1 
1 2 3 2 4 2 1 5 1 
1 2 1 3 1 4 1 5 1 
1 2 1 3 1 4 1 5 1 
1 2 1 3 1 4 1 5 1 
1 2 1 3 1 4 1 5 1 
1 2 1 3 1 4 1 5 1 
1 2 1 3 1 4 1 5 1 

result:

ok 9 lines

Test #2:

score: -100
Runtime Error

input:

28668
2
0 2 1
2
0 0 1
2
0 0 0
2
1 0 1
2
1 0 0
2
1 2 0
3
0 2 1 3 1
3
0 0 1 3 1
3
0 0 0 3 1
3
0 0 0 0 1
3
0 0 0 0 0
3
1 0 1 3 1
3
1 0 0 3 1
3
1 0 0 0 1
3
1 0 0 0 0
3
1 2 0 3 1
3
1 2 0 0 1
3
1 2 0 0 0
3
1 2 1 0 1
3
1 2 1 0 0
3
1 2 1 3 0
3
0 2 3 2 1
3
0 0 3 2 1
3
0 0 0 2 1
3
1 0 3 2 1
3
1 0 0 2 1
3
1 2 ...

output:


result: