QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#84830 | #5665. AA Country and King Dreamoon | runewrz | WA | 48ms | 3344kb | C++17 | 1.4kb | 2023-03-06 20:01:17 | 2023-03-06 20:01:24 |
Judging History
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'