QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#84830#5665. AA Country and King DreamoonrunewrzWA 48ms3344kbC++171.4kb2023-03-06 20:01:172023-03-06 20:01:24

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-06 20:01:24]
  • 评测
  • 测评结果:WA
  • 用时:48ms
  • 内存:3344kb
  • [2023-03-06 20:01:17]
  • 提交

answer

#include <bits/stdc++.h>

#define fo(i, x, y) for (int i = int(x); i <= int(y); ++i)
#define fd(i, x, y) for (int i = int(x); i >= int(y); --i)
#define fi first
#define se second

using namespace std;
using pii = pair<int, int>;
using i64 = long long;

constexpr int inf = 1e9;

void work()
{
	int n;
	cin >> n;
	vector<int> a(n * 2);
	set<int> num;
	fo(i, 1, n)
		num.emplace(i);
	int s0 = 0, l = 0, r = 0;
	fo(i, 1, n * 2 - 1)
	{
		cin >> a[i];
		if (i == 1) a[1] = 1;
		if (!a[i])
		{
			s0++;
			if (!l) l = i;
			r = i;
		}
		if (num.count(a[i]))
			num.erase(a[i]);
	}
	if (!count(a.begin() + 1, a.end(), 0))
	{
		fo(i, 1, n * 2 - 1)
			cout << a[i] << " \n"[i + 1 == n * 2];
		return;
	}
	int lim = 0;
	fd(i, n * 2 - 1, 1)
		if (a[i])
			lim = a[i];
		else break;
	vector<int> st(n + 5);
	int top = 0;
	st[top++] = inf;
	fo(i, 1, n * 2 - 1)
		if (a[i])
		{
			if (top >= 2 && a[i] == st[top - 2])
				top--;
			else
				st[top++] = a[i];
		}
		else break;
	fo(i, l, r)
	{
		if (num.size() && (!top || st[top - 1] == lim || *num.begin() < st[top - 2]))
		{
			st[top++] = *num.begin();
			a[i] = *num.begin();
			num.erase(num.begin());
		}
		else
		{
			top--;
			a[i] = st[top - 1];
		}
	}
	fo(i, 1, 2 * n - 1)
		cout << a[i] << " \n"[i + 1 == n * 2];
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
#ifdef LC
	freopen("t.in", "r", stdin);
	freopen("t.out", "w", stdout);
#endif
	int T;
	cin >> T;
	while (T--)
		work();
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3336kb

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
Wrong Answer
time: 48ms
memory: 3344kb

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:

1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 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 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 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 3 2 1
1 1000000000 3 2 1
1 3 1 2 1
1 1000000000 3 2 1
1 3 1 2 1
1 2 3 2 1
1 2 3 2 1
1 2 3 2 1
1 2 3 2 1
1 3 1 ...

result:

wrong answer 23rd lines differ - expected: '1 2 3 2 1', found: '1 1000000000 3 2 1'