QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#72251#5430. Triangeltalswift14 59ms9372kbC++231.4kb2023-01-15 11:13:042023-01-15 11:13:04

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-15 11:13:04]
  • 评测
  • 测评结果:14
  • 用时:59ms
  • 内存:9372kb
  • [2023-01-15 11:13:04]
  • 提交

answer

#include <bits/stdc++.h>
#define N 510000
using namespace std;
int n, ans[N];
pair<int, int> a[N];
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; i++)
    cin >> a[i].first, a[i].second = i;
  sort(a + 1, a + n + 1);
  for (int i = 1; i < n; i++) {
    if (i >= a[n].first && i + a[i].first < n &&
        a[i + a[i].first].first <= n - (i + a[i].first)) {
      for (int j = 1; j <= i; j++)
        ans[a[j].second] = 1;
      for (int j = i + 1; j <= i + a[i].first; j++)
        ans[a[j].second] = 3;
      for (int j = i + a[i].first + 1; j <= n; j++)
        ans[a[j].second] = 2;
      cout << "YES" << '\n';
      for (int j = 1; j <= n; j++)
        cout << ans[j];
      cout << '\n';
      exit(0);
    } else {
      int l = i + a[n].first,
          r = min((int)(upper_bound(a + 1, a + n + 1, make_pair(i, n)) - a - 1),
                  n - a[i].first);
      if (l <= r && l < n) {
        for (int j = 1; j <= i; j++)
          ans[a[j].second] = 1;
        for (int j = i + 1; j <= l; j++)
          ans[a[j].second] = 2;
        for (int j = l + 1; j <= n; j++)
          ans[a[j].second] = 3;
        cout << "YES" << '\n';
        for (int j = 1; j <= n; j++)
          cout << ans[j];
        cout << '\n';
        exit(0);
      }
    }
  }
  cout << "NO" << '\n';
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 14
Accepted

Test #1:

score: 14
Accepted
time: 2ms
memory: 5360kb

input:

3
1 1 1

output:

YES
132

result:

ok Correct

Test #2:

score: 0
Accepted
time: 2ms
memory: 3500kb

input:

3
2 2 2

output:

NO

result:

ok Correct

Test #3:

score: 0
Accepted
time: 1ms
memory: 5584kb

input:

10
1 1 1 1 1 1 1 1 1 1

output:

YES
1322222222

result:

ok Correct

Test #4:

score: 0
Accepted
time: 0ms
memory: 5444kb

input:

10
3 3 3 3 3 3 3 3 3 3

output:

YES
1113332222

result:

ok Correct

Test #5:

score: 0
Accepted
time: 0ms
memory: 3312kb

input:

10
4 4 4 4 4 4 4 4 4 4

output:

NO

result:

ok Correct

Test #6:

score: 0
Accepted
time: 16ms
memory: 7768kb

input:

99999
33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 33333 ...

output:

YES
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok Correct

Test #7:

score: 0
Accepted
time: 49ms
memory: 9372kb

input:

500000
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 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...

output:

YES
13222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...

result:

ok Correct

Test #8:

score: 0
Accepted
time: 56ms
memory: 9320kb

input:

500000
166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666 166666...

output:

YES
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok Correct

Test #9:

score: 0
Accepted
time: 59ms
memory: 7304kb

input:

500000
166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667 166667...

output:

NO

result:

ok Correct

Test #10:

score: 0
Accepted
time: 47ms
memory: 7892kb

input:

500000
500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000 500000...

output:

NO

result:

ok Correct

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 16
Accepted
time: 2ms
memory: 5428kb

input:

3
1 1 1

output:

YES
132

result:

ok Correct

Test #12:

score: 0
Accepted
time: 1ms
memory: 3348kb

input:

3
1 2 2

output:

NO

result:

ok Correct

Test #13:

score: 0
Accepted
time: 2ms
memory: 5416kb

input:

9
3 3 3 3 3 3 3 3 3

output:

YES
111333222

result:

ok Correct

Test #14:

score: -16
Wrong Answer
time: 2ms
memory: 5380kb

input:

10
2 3 1 4 3 1 4 3 4 2

output:

YES
1213213232

result:

wrong answer Max of group 3 (4) was bigger than size of the next group (3)

Subtask #3:

score: 0
Wrong Answer

Test #24:

score: 11
Accepted
time: 2ms
memory: 5416kb

input:

4
1 1 1 1

output:

YES
1322

result:

ok Correct

Test #25:

score: -11
Wrong Answer
time: 1ms
memory: 5548kb

input:

5
2 2 1 1 1

output:

YES
33122

result:

wrong answer Max of group 3 (2) was bigger than size of the next group (1)

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%