QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#83605	#1873. Array	woxiangbaile^#	WA	183ms	8040kb	C++14	1.6kb	2023-03-02 17:50:22	2023-03-02 17:50:23

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-02 17:50:23]
评测

测评结果：WA
用时：183ms
内存：8040kb

查看

[2023-03-02 17:50:22]
提交

answer

#include <bits/stdc++.h>

using namespace std;

#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl

const int N = 2e5 + 10;

int read() {
  int x = 0, f = 1; char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
  return x * f;
}

int n, b[N], L[N], p[N], a[N], cnt, len;
bool tag[N];

void solve() {
  n = read(), cnt = 0, len = n;
  rep(i, 1, n) b[i] = read(), L[i] = 0, p[i] = -1, tag[i] = false;
  rep(i, 1, n) if (b[i] < i) return printf("-1\n"), void();
  rep(i, 1, n) if (b[i] <= n) len = min(len, b[i] - i + 1);
  rep(i, 0, n - 1) if (b[i] < b[i + 1]) {
    rep(j, b[i], b[i + 1] - 1) L[j] = i + 1;
    tag[i] = true, p[b[i + 1]] = i;
  }
  priority_queue <int, vector <int>, greater <int> > q;
  a[0] = cnt = 1;
  rep(i, 1, n) {
    if (~p[i]) a[i] = a[p[i]];
    else if (cnt < len) a[i] = ++ cnt;
    else {
      if (q.size() && L[i] <= q.top()) a[i] = a[q.top()], q.pop();
      else return printf("-1\n"), void();
    }
    // cout << "i, a[i] = " << i << ' ' << a[i] << endl;
    if (q.size() && q.top() < L[i]) return printf("-1\n"), void();
    if (!tag[i]) q.push(i);
  }
  rep(i, 1, n) printf("%d%c", a[i], " \n"[i == n]);
}

int main() {
  for (int tc = read(); tc; -- tc) {
    solve();
  }
  return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 2ms

memory: 3564kb

input:

3
4
3 3 5 5
7
4 6 6 7 8 8 8
5
2 3 4 4 6

output:

2 2 1 1
2 3 4 1 3 2 4
-1

result:

ok 233

Test #2:

score: -100

Wrong Answer

time: 183ms

memory: 8040kb

input:

23198
7
1 2 3 4 5 6 7
7
1 2 3 4 5 6 8
7
1 2 3 4 5 7 7
7
1 2 3 4 5 7 8
7
1 2 3 4 5 8 8
7
1 2 3 4 6 6 7
7
1 2 3 4 6 6 8
7
1 2 3 4 6 7 7
7
1 2 3 4 6 7 8
7
1 2 3 4 6 8 8
7
1 2 3 4 7 7 7
7
1 2 3 4 7 7 8
7
1 2 3 4 7 8 8
7
1 2 3 4 8 8 8
7
1 2 3 5 5 6 7
7
1 2 3 5 5 6 8
7
1 2 3 5 5 7 7
7
1 2 3 5 5 7 8
7
1 2 ...

output:

1 1 1 1 1 1 1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-...

result:

wrong answer wrong answer, the correct answer is -1