QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#732691#5665. AA Country and King DreamoonAshbourneRE 1ms7716kbC++231.5kb2024-11-10 15:34:332024-11-10 15:34:34

Judging History

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

  • [2024-11-10 15:34:34]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:7716kb
  • [2024-11-10 15:34:33]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int a[N], Ton[N], fa[N];
void solve(){
	int n, l = 0, r = n;
	cin >> n;
	vector<int> vis(n + 100);
	for(int i = 1; i <= n; ++ i) Ton[i] = 0, fa[i] = 0;
	// vector<int> a(2 * n + 1);
	a[0] = 1e14; a[2 * n] = 1e14; 
	for(int i = 1; i <= 2 * n - 1; ++ i) cin >> a[i];
	for(int i = 1; i <= 2 * n - 1; ++ i){
	    vis[a[i]] = 1;
		if(a[i - 1] && !a[i]) l = i;
		if(!a[i] && a[i + 1]) r = i;
	}
	int lx, rx;
	vis[n + 1] = 1;
	for(int i = 1; i <= n; ++ i){
		if(vis[i - 1] && !vis[i]) lx = i;
		if(!vis[i] && vis[i + 1]) rx = i;
	}
	// cout << l << " " << r << endl;
	for(int i = r + 1; i <= 2 * n - 1; ++ i) Ton[a[i]]++;
	if(l == 1 && r == 2 * n - 1){
		for(int i = 1; i <= 2 * n - 1; ++ i){
			if(i % 2 == 1) a[i] = 1;
			else a[i] = i / 2 + 1;
			cout << a[i] << " ";
 		}
 		cout << endl;
		return;
	}
	if(l == 1){
		a[1] = a[n];
		l++;
	}
	// cout << l << " " << r << endl;
	fa[a[1]] = 1e14;
	for(int i = 2; i <= l - 1; ++ i){
		if(!fa[a[i]]) fa[a[i]] = a[i - 1];
	}
	// cout << fa[3] << endl; 
	for(int i = l; i <= r; ++ i){
		int rd = fa[a[i - 1]];
		// cout << rd << endl;
		bool flag = 1;
		if(!rd || Ton[a[i - 1]]) flag = 0;
		// cout << flag  << endl;
		if(flag && (rd < lx || lx > rx)){
			a[i] = rd;
		}else{
			a[i] = lx++;
			fa[a[i]] = a[i - 1];
		}
	}
	for(int i = 1; i <= 2 * n - 1; ++i ){
		cout << a[i] << " ";
	}
	cout << endl;
}
signed main(){
	ios::sync_with_stdio(0);
	int T;
	cin >> T;
	while(T--) solve();
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7716kb

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:

2 2 1 
0 2 1 
1 2 1 
1 2 1 
1 2 1 
1 2 0 
1 2 1 3 1 
1 2 1 3 1 
0 2 3 3 1 
0 2 3 2 1 
1 2 1 3 1 
1 2 1 3 1 
1 2 1 3 1 
1 2 1 3 1 
1 2 1 3 1 
1 2 0 3 1 
1 2 1 3 1 
1 2 1 3 1 
1 2 1 3 1 
1 2 1 3 1 
1 2 1 3 0 
3 2 3 2 1 
3 0 3 2 1 
0 3 4 2 1 
1 0 3 2 1 
1 3 1 2 1 
1 2 3 2 1 
1 2 3 0 1 
1 2 3 0 3 
1 2 3...

result: