QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#72487#5430. Triangeltalabcdefg0 66ms9332kbC++174.4kb2023-01-15 19:50:462023-01-15 19:50:50

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 19:50:50]
  • 评测
  • 测评结果:0
  • 用时:66ms
  • 内存:9332kb
  • [2023-01-15 19:50:46]
  • 提交

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;
    // dbg(l, r);
    // dbg(n-r,a[r].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);
  }
  re (l, n - 2) {
    int r = n - a[l].first + 1;
    // dbg(l, r);
    if (r <= l) break;
    if (r - l < a[r].first) continue;
    cout << "YES\n";
    re (j, l) ans[a[j].second] = 1;
    rep (j, l + 1, r) ans[a[j].second] = 3;
    rep (j, r + 1, n) ans[a[j].second] = 2;
    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: 0
Wrong Answer

Test #1:

score: 14
Accepted
time: 1ms
memory: 3432kb

input:

3
1 1 1

output:

YES
123

result:

ok Correct

Test #2:

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

input:

3
2 2 2

output:

NO

result:

ok Correct

Test #3:

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

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: 3464kb

input:

10
3 3 3 3 3 3 3 3 3 3

output:

YES
1112223333

result:

ok Correct

Test #5:

score: -14
Wrong Answer
time: 0ms
memory: 3424kb

input:

10
4 4 4 4 4 4 4 4 4 4

output:

YES
1333333222

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #11:

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

input:

3
1 1 1

output:

YES
123

result:

ok Correct

Test #12:

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

input:

3
1 2 2

output:

YES
133

result:

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

Subtask #3:

score: 0
Wrong Answer

Test #24:

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

input:

4
1 1 1 1

output:

YES
1233

result:

ok Correct

Test #25:

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

input:

5
2 2 1 1 1

output:

YES
33112

result:

ok Correct

Test #26:

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

input:

3
3 1 1

output:

NO

result:

ok Correct

Test #27:

score: 0
Accepted
time: 66ms
memory: 9332kb

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: 2ms
memory: 3468kb

input:

9
3 3 3 3 3 3 3 3 3

output:

YES
111222333

result:

ok Correct

Test #29:

score: 0
Accepted
time: 55ms
memory: 9316kb

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: -11
Wrong Answer
time: 0ms
memory: 3532kb

input:

8
3 3 3 3 3 3 3 3

output:

YES
13333322

result:

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

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%