QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#72247#5430. Triangeltalabcdefg14 78ms13048kbC++174.0kb2023-01-15 11:02:282023-01-15 11:02:29

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:02:29]
  • 评测
  • 测评结果:14
  • 用时:78ms
  • 内存:13048kb
  • [2023-01-15 11:02:28]
  • 提交

answer

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <forward_list>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double lf;

// #define int ll
#define rep(i, f, t) for (int i = (f), ed##i = (t); i <= ed##i; ++i)
#define re(i, t) rep (i, 1, t)
#define per(i, t, f) for (int i = (t), ed##i = (f); i >= ed##i; --i)
#define ste(i, f, t, s) for (int i = (f), ed##i = (t); i <= ed##i; i += s)
#define each(i, x) for (auto &&i : (x))
#define nxt(i, f, g) for (int i = g.h[f]; i; i = g.e[i].n)
#define umod(x) ((x) >= mo && ((x) -= mo))
#define dmod(x) ((x) < 0 && ((x) += mo))
#define y1 y1__
#define fio(x) (freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout))

__attribute__((always_inline)) inline void __print(signed x) { cerr << x; }
__attribute__((always_inline)) inline void __print(long x) { cerr << x; }
__attribute__((always_inline)) inline void __print(long long x) { cerr << x; }
__attribute__((always_inline)) inline void __print(unsigned x) { cerr << x; }
__attribute__((always_inline)) inline void __print(unsigned long x) { cerr << x; }
__attribute__((always_inline)) inline void __print(unsigned long long x) { cerr << x; }
__attribute__((always_inline)) inline void __print(float x) { cerr << x; }
__attribute__((always_inline)) inline void __print(double x) { cerr << x; }
__attribute__((always_inline)) inline void __print(long double x) { cerr << x; }
__attribute__((always_inline)) inline void __print(char x) { cerr << '\'' << x << '\''; }
__attribute__((always_inline)) inline void __print(char *x) { cerr << '\"' << x << '\"'; }
__attribute__((always_inline)) inline void __print(const char *x) { cerr << '\"' << x << '\"'; }
__attribute__((always_inline)) inline void __print(const string &x) { cerr << '\"' << x << '\"'; }
__attribute__((always_inline)) inline void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{', __print(x.first), cerr << ',', __print(x.second), cerr << '}';
}
template <typename T>
void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
__attribute__((always_inline)) inline void _print() { cerr << "]\033[0m\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
#ifndef ONLINE_JUDGE
#define dbg(x...) (cerr << "\033[34m[" << #x << "] = [", _print(x))
#else
#define dbg(x...) (0)
#endif

template <class T, class E>
__attribute__((always_inline)) inline void up(T &x, E &&y) {
  if (x < y) x = y;
}
template <class T, class E>
__attribute__((always_inline)) inline void down(T &x, E &&y) {
  if (y < x) x = y;
}

const int N = 1e6 + 9;
int n, ans[N];
pair<int, int> a[N];

signed main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  re (i, n) cin >> a[i].first, a[i].second = i;
  sort(a + 1, a + n + 1);
  rep (l, a[n].first, n - 2) {
    int r = l + a[l].first;
    if (r > n) break;
    if (n - r < a[r].first) continue;
    cout << "YES\n";
    re (j, l) ans[a[j].second] = 1;
    rep (j, l + 1, r) ans[a[j].second] = 2;
    rep (j, r + 1, n) ans[a[j].second] = 3;
    re (j, n) 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: 0ms
memory: 5360kb

input:

3
1 1 1

output:

YES
123

result:

ok Correct

Test #2:

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

input:

3
2 2 2

output:

NO

result:

ok Correct

Test #3:

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

input:

10
1 1 1 1 1 1 1 1 1 1

output:

YES
1233333333

result:

ok Correct

Test #4:

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

input:

10
3 3 3 3 3 3 3 3 3 3

output:

YES
1112223333

result:

ok Correct

Test #5:

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

input:

10
4 4 4 4 4 4 4 4 4 4

output:

NO

result:

ok Correct

Test #6:

score: 0
Accepted
time: 15ms
memory: 6212kb

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: 53ms
memory: 11056kb

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

result:

ok Correct

Test #8:

score: 0
Accepted
time: 58ms
memory: 11588kb

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: 49ms
memory: 9412kb

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: 42ms
memory: 7784kb

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: 3ms
memory: 5420kb

input:

3
1 1 1

output:

YES
123

result:

ok Correct

Test #12:

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

input:

3
1 2 2

output:

NO

result:

ok Correct

Test #13:

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

input:

9
3 3 3 3 3 3 3 3 3

output:

YES
111222333

result:

ok Correct

Test #14:

score: 0
Accepted
time: 3ms
memory: 5540kb

input:

10
2 3 1 4 3 1 4 3 4 2

output:

YES
1213213331

result:

ok Correct

Test #15:

score: 0
Accepted
time: 3ms
memory: 3372kb

input:

10
1 9 5 4 3 9 4 6 5 1

output:

NO

result:

ok Correct

Test #16:

score: -16
Wrong Answer
time: 3ms
memory: 3340kb

input:

10
5 3 2 2 3 2 5 3 3 3

output:

NO

result:

wrong answer Contestant said no, but judge found a solution

Subtask #3:

score: 0
Wrong Answer

Test #24:

score: 11
Accepted
time: 1ms
memory: 5588kb

input:

4
1 1 1 1

output:

YES
1233

result:

ok Correct

Test #25:

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

input:

5
2 2 1 1 1

output:

YES
33112

result:

ok Correct

Test #26:

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

input:

3
3 1 1

output:

NO

result:

ok Correct

Test #27:

score: 0
Accepted
time: 78ms
memory: 13048kb

input:

500000
1 2 3 1 2 3 2 2 3 3 1 1 2 3 1 1 2 3 1 3 2 1 2 3 1 3 3 3 1 2 3 2 2 2 1 3 1 2 2 2 2 3 3 1 3 3 1 2 2 3 1 2 3 2 2 1 1 1 3 2 3 1 1 2 3 1 2 1 1 1 1 1 1 3 3 1 2 2 2 2 3 2 2 1 3 3 3 2 1 3 1 1 1 1 2 3 3 3 3 2 2 3 1 1 1 2 2 1 3 3 3 2 2 3 3 1 2 3 2 3 2 2 2 2 2 3 1 3 2 1 2 1 2 2 2 1 1 1 1 2 1 3 1 1 1 1 2...

output:

YES
13313333331233333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333...

result:

ok Correct

Test #28:

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

input:

9
3 3 3 3 3 3 3 3 3

output:

YES
111222333

result:

ok Correct

Test #29:

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

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

result:

ok Correct

Test #30:

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

input:

8
3 3 3 3 3 3 3 3

output:

NO

result:

ok Correct

Test #31:

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

input:

8
2 2 3 2 3 2 1 3

output:

YES
11323213

result:

ok Correct

Test #32:

score: -11
Wrong Answer
time: 2ms
memory: 3376kb

input:

6
1 2 3 2 2 1

output:

NO

result:

wrong answer Contestant said no, but judge found a solution

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%