QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#86586#4800. Oscar's Round Must Have a Constructive Problemchimera#AC ✓1671ms17524kbC++173.4kb2023-03-10 10:47:112023-03-10 10:47:14

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-10 10:47:14]
  • 评测
  • 测评结果:AC
  • 用时:1671ms
  • 内存:17524kb
  • [2023-03-10 10:47:11]
  • 提交

answer

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <tuple>
#include <utility>
#define greedy int
#define mindset main()

using namespace std;
#define FOR(a,b,c) for(int a = b; a < (c); a++)
#define FORR(a,b,c) for(int a = b; a > (c); a--)
 
#define READ(x) long long x;cin>>x;
#define READAR(x,n) vll x(n); FOR(readar,0,n) cin >> x[readar];

#define speedfirst ios_base::sync_with_stdio(false); cin.tie(NULL); 
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef tuple<ll,ll,ll> tll;

ll MOD = 998244353;

/*//Combinatorics mod MOD
vll FACT(1e5);

ll fastexp(ll a, ll p) {
    ll r = 1;
    while(p) {
        if(p&1) r = r*a % MOD;
        a = a*a % MOD;
        p >>= 1;
    }
    return r;
}

ll modinv(ll x) {
    return fastexp(x,MOD-2);
}

void DOFACTS() {
    FACT[0] = 1;
    FOR(i,1,FACT.size()) {
        FACT[i] = i*FACT[i-1] % MOD;
    }
}

ll gcd(ll a, ll b) {
   if (b == 0)
   return a;
   return gcd(b, a % b);
}
*/

//segment tree, courtesy of https://cp-algorithms.com/data_structures/segment_tree.html
/*
int tree[4*200000];
void build(int v, int tl, int tr) {
    if (tl == tr) {
        tree[v] = 0;
    } else {
        int tm = (tl + tr) / 2;
        build(v*2, tl, tm);
        build(v*2+1, tm+1, tr);
        tree[v] = tree[v*2] + tree[v*2+1];
    }
}
int sum(int v, int tl, int tr, int l, int r) {
    if (l > r) 
        return 0;
    if (l == tl && r == tr) {
        return tree[v];
    }
    int tm = (tl + tr) / 2;
    return sum(v*2, tl, tm, l, min(r, tm))
           + sum(v*2+1, tm+1, tr, max(l, tm+1), r);
}
void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        tree[v] = new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        tree[v] = tree[v*2] + tree[v*2+1];
    }
}
void add(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        tree[v] += new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            add(v*2, tl, tm, pos, new_val);
        else
            add(v*2+1, tm+1, tr, pos, new_val);
        tree[v] = tree[v*2] + tree[v*2+1];
    }
}
*/


greedy mindset {
    speedfirst;

    READ(T);
    FOR(t,0,T) {
        READ(N); READAR(A, N);
        map<ll,vll> CA;

        FOR(i,0,N) {
            CA[A[i]].push_back(i);
        }

        if(CA[A[0]].size() == N) {
            cout << "NO\n"; continue;
        }

        vll X(N);
        FOR(i,0,N) X[i] = i+1;

        sort(X.begin(), X.end(), [&](ll x, ll y) {
            return (CA[x].size() > CA[y].size()) || ((CA[x].size() == CA[y].size()) && (x > y));
        });

        vll P(N,-1);

        FOR(i,0,N) {
            if(!(CA[i].size())) CA.erase(i);
        }

        FOR(i,0,N) {
            auto it = CA.begin();
            if((*it).first == X[i]) ++it;
            P[(*it).second.back()] = X[i];
            (*it).second.pop_back();
            if(!(*it).second.size()) {
                CA.erase(it);
            }
        }

        cout << "YES\n";

        FOR(i,0,N) {
            cout << P[i] << (i == N-1 ? '\n' : ' ');
        }

        
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3452kb

input:

3
3
3 3 3
3
3 2 1
6
1 1 4 5 1 4

output:

NO
YES
2 1 3
YES
6 5 3 2 4 1

result:

ok ok

Test #2:

score: 0
Accepted
time: 70ms
memory: 3448kb

input:

50069
1
1
2
1 1
2
1 2
2
2 1
2
2 2
3
1 1 1
3
1 1 2
3
1 1 3
3
1 2 1
3
1 2 2
3
1 2 3
3
1 3 1
3
1 3 2
3
1 3 3
3
2 1 1
3
2 1 2
3
2 1 3
3
2 2 1
3
2 2 2
3
2 2 3
3
2 3 1
3
2 3 2
3
2 3 3
3
3 1 1
3
3 1 2
3
3 1 3
3
3 2 1
3
3 2 2
3
3 2 3
3
3 3 1
3
3 3 2
3
3 3 3
4
1 1 1 1
4
1 1 1 2
4
1 1 1 3
4
1 1 1 4
4
1 1 2 1
...

output:

NO
NO
YES
2 1
YES
1 2
NO
NO
YES
3 2 1
YES
2 3 1
YES
3 1 2
YES
2 3 1
YES
3 1 2
YES
2 1 3
YES
3 2 1
YES
3 2 1
YES
1 3 2
YES
3 2 1
YES
1 3 2
YES
3 1 2
NO
YES
1 3 2
YES
1 2 3
YES
1 2 3
YES
3 1 2
YES
1 2 3
YES
2 3 1
YES
2 3 1
YES
2 1 3
YES
2 1 3
YES
1 3 2
YES
2 1 3
YES
1 2 3
NO
NO
YES
3 4 2 1
YES
2 4 3 1...

result:

ok ok

Test #3:

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

input:

100000
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok ok

Test #4:

score: 0
Accepted
time: 157ms
memory: 3416kb

input:

50000
10
3 3 3 3 3 6 3 3 3 3
10
4 5 5 5 5 5 5 5 5 5
10
8 8 8 8 8 8 8 1 8 8
10
6 6 6 6 6 6 6 6 6 2
10
4 4 4 5 4 4 4 4 4 4
10
4 5 4 4 4 10 10 4 5 10
10
8 10 10 6 4 8 4 7 10 4
10
8 8 8 8 8 8 8 8 8 8
10
4 4 4 9 10 10 10 10 4 1
10
4 4 4 4 4 1 4 4 4 4
10
5 5 5 5 6 6 5 6 5 6
10
10 10 10 10 10 10 10 10 10 1...

output:

YES
1 2 4 5 7 3 8 9 10 6
YES
5 1 2 3 6 7 8 9 10 4
YES
2 3 4 5 6 7 9 8 10 1
YES
1 3 4 5 7 8 9 10 2 6
YES
1 2 3 4 6 7 8 9 10 5
YES
7 6 8 9 5 1 2 10 4 3
YES
5 1 2 4 7 9 8 6 3 10
NO
YES
7 8 1 4 2 3 5 6 9 10
YES
2 3 5 6 7 4 8 9 10 1
YES
4 7 8 9 1 2 10 3 6 5
NO
NO
YES
1 2 4 3 5 10 7 6 8 9
YES
1 7 10 2 6 9...

result:

ok ok

Test #5:

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

input:

5000
100
37 37 37 58 58 58 58 58 58 58 37 58 37 37 37 58 37 37 37 37 58 58 37 37 37 37 58 37 58 58 58 58 37 58 58 58 37 58 37 37 37 37 58 37 37 37 58 37 37 58 37 37 37 58 37 37 58 37 58 58 58 58 37 37 58 58 58 37 37 58 58 37 37 58 37 58 58 37 58 58 58 37 58 58 37 58 58 58 37 58 58 58 37 58 58 37 58 ...

output:

YES
53 54 55 1 2 3 4 5 6 7 56 8 57 59 60 9 61 62 63 64 10 11 65 66 67 68 12 69 13 14 15 16 70 17 18 19 71 20 72 73 74 75 21 76 77 78 22 79 80 23 81 82 83 24 84 85 25 86 26 27 28 29 87 88 30 31 32 89 90 33 34 91 92 35 93 36 38 94 39 40 41 95 42 43 96 44 45 46 97 47 48 49 98 50 51 99 52 100 58 37
YES
...

result:

ok ok

Test #6:

score: 0
Accepted
time: 547ms
memory: 3616kb

input:

500
1000
452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452...

output:

NO
NO
NO
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

result:

ok ok

Test #7:

score: 0
Accepted
time: 829ms
memory: 4736kb

input:

50
10000
9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9...

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok ok

Test #8:

score: 0
Accepted
time: 1019ms
memory: 6804kb

input:

20
25000
2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2...

output:

YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok ok

Test #9:

score: 0
Accepted
time: 1671ms
memory: 10108kb

input:

10
50000
32825 31708 22702 32825 22702 31708 32825 32825 9333 31708 32825 46864 22702 32825 31708 31708 22702 22702 31708 46864 9333 9333 1785 31708 22702 9333 1785 32825 31708 22702 46864 32825 9333 46864 9333 35050 31708 1785 46864 9333 32825 1785 22702 31708 22702 1785 46864 32825 1785 35050 9333...

output:

YES
14229 21372 28521 14230 28522 21373 14231 14232 35694 21374 14233 1 28523 14234 21375 21376 28524 28525 21377 2 35695 35696 42870 21378 28526 35697 42871 14235 21379 28527 3 14236 35698 4 35699 7089 21380 42872 5 35700 14237 42873 28528 21381 28529 42874 6 14238 42875 7090 35701 7091 28530 28531...

result:

ok ok

Test #10:

score: 0
Accepted
time: 1306ms
memory: 17524kb

input:

5
100000
25575 25575 25575 25575 38740 38740 25575 38740 25575 38740 25575 25575 25575 38740 38740 38740 25575 38740 25575 25575 25575 25575 38740 38740 38740 38740 25575 25575 25575 38740 38740 25575 25575 38740 25575 38740 25575 38740 38740 25575 38740 38740 25575 38740 25575 25575 38740 38740 255...

output:

YES
50004 50005 50006 50007 2 3 50008 4 50009 5 50010 50011 50012 6 7 8 50013 9 50014 50015 50016 50017 10 11 12 13 50018 50019 50020 14 15 50021 50022 16 50023 17 50024 18 19 50025 20 21 50026 22 50027 50028 23 24 50029 50030 50031 25 26 27 50032 50033 50034 50035 50036 50037 28 29 50038 30 50039 3...

result:

ok ok