QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#13236#1439. Football MatchQingyuAC ✓3ms3732kbC++203.3kb2021-08-29 15:12:522022-05-17 01:39:43

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-17 01:39:43]
  • 评测
  • 测评结果:AC
  • 用时:3ms
  • 内存:3732kb
  • [2021-08-29 15:12:52]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/stack:16777216")
#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <cassert>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
#include <time.h>
#include <complex>
using namespace std;

#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)
#define FILL(A,value) memset(A,value,sizeof(A))

#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define Pi 3.14159265358979
#define x0 ikjnrmthklmnt
#define y0 lkrjhkltr
#define y1 ewrgrg

typedef long long Int;
typedef unsigned long long UInt;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<Int, Int> PLL;
typedef pair<double, double> PDD;
typedef complex<double> base;

const int INF = 1000000000;
const int BASE = 1000000007;
const int MAX = 200000;
const int MAX2 = 7777;
const int MAXE = 100000;
const int ADD = 1000000;
const int MOD = 1000000007;
const int CNT = 800;

set<pair<VI, VI> > S;

pair<VI, VI> small(int a, int b)
{
    for(auto it = S.begin(); it != S.end(); ++it)
    {
        int x = it->first.size();
        int y = it->second.size();

        if (a >= x && b >= y && (a - x) % 2 == 0 && (b - y) % 2 == 0)
        {
            return *it;
        }

    }
    return {{}, {}};
}

pair<VI, VI> addYes(pair<VI, VI> a, int k)
{
    int s = 0;
    FOR(i,0,SZ(a.first))
        s += a.first[i];
    FOR(i,0,SZ(a.second))
        s += a.second[i];


    FOR(i,0,k)
    {
        a.first.push_back(s);
    }
    return a;
}

pair<VI, VI> addNo(pair<VI, VI> a, int k)
{
    int s = 0;
    FOR(i,0,SZ(a.first))
        s += a.first[i];
    FOR(i,0,SZ(a.second))
        s += a.second[i];

    FOR(i,0,k)
    {
        a.second.push_back(s + 1);
    }
    return a;
}

int main()
{

    S.insert( MP( VI({1}) , VI({}) ) );
    S.insert( MP( VI({}) , VI({1, 2}) ));
    S.insert( MP( VI({}), VI({1,2,4}) ));
    S.insert( MP( VI({1,7,5,9}), VI({3}) ) );
    S.insert( MP( VI({4}), VI({1,1,2}) ) );
    S.insert( MP( VI({1, 1, 1}), VI({2}) ) );

    int n;
    cin >> n;

    string s;
    cin >> s;

    VI A, B;

    FOR(i,0,SZ(s))
    {
        if (s[i] == 'Y')
        {
            A.push_back(i);
        }
        else
        {
            B.push_back(i);
        }
    }

    pair<VI, VI> x = small(SZ(A) , SZ(B));

    if (x.first.size() == 0 && x.second.size() == 0)
    {
        cout << "NO" << endl;
        return 0;
    }

    x = addYes(x , SZ(A) - x.first.size());
    x = addNo(x , SZ(B) - x.second.size());



    cout << "YES" << endl;

    int sy = 0;
    int sn = 0;

    VI res;

    FOR(i,0,SZ(s))
    {
        if (s[i] == 'Y')
        {
            res.push_back(x.first[sy ++]);
        }
        else
        {
            res.push_back(x.second[sn ++]);
        }
    }


    FOR(i,0,SZ(res))
    {
        cout << res[i] << (i + 1 < n ? ' ' : '\n');
    }




    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
YNNY

output:

YES
3 1 2 3

result:

ok OK

Test #2:

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

input:

3
NNN

output:

YES
1 2 4

result:

ok OK

Test #3:

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

input:

4
NNNN

output:

YES
1 2 4 4

result:

ok OK

Test #4:

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

input:

5
NNNNN

output:

YES
1 2 4 8 8

result:

ok OK

Test #5:

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

input:

3
YNN

output:

YES
1 2 2

result:

ok OK

Test #6:

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

input:

4
NNYN

output:

YES
1 1 4 2

result:

ok OK

Test #7:

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

input:

5
NNYNN

output:

YES
2 2 1 2 2

result:

ok OK

Test #8:

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

input:

3
YYN

output:

NO

result:

ok OK

Test #9:

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

input:

4
NNYY

output:

YES
1 2 3 3

result:

ok OK

Test #10:

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

input:

5
YNYNN

output:

YES
7 1 7 2 4

result:

ok OK

Test #11:

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

input:

3
YYY

output:

YES
1 1 1

result:

ok OK

Test #12:

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

input:

4
YYNY

output:

YES
1 1 2 1

result:

ok OK

Test #13:

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

input:

5
YYNNY

output:

YES
1 1 4 4 1

result:

ok OK

Test #14:

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

input:

4
YYYY

output:

NO

result:

ok OK

Test #15:

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

input:

5
YNYYY

output:

YES
1 3 7 5 9

result:

ok OK

Test #16:

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

input:

5
YYYYY

output:

YES
1 1 1 1 1

result:

ok OK

Test #17:

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

input:

49
YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY

output:

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

ok OK

Test #18:

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

input:

50
YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY

output:

NO

result:

ok OK

Test #19:

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

input:

49
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN

output:

YES
1 2 4 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8

result:

ok OK

Test #20:

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

input:

50
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN

output:

YES
1 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4

result:

ok OK

Test #21:

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

input:

50
YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYN

output:

YES
1 1 1 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 2

result:

ok OK

Test #22:

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

input:

49
YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYY

output:

YES
1 7 5 9 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 3 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25

result:

ok OK

Test #23:

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

input:

50
NNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNN

output:

YES
1 1 2 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 4 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9

result:

ok OK

Test #24:

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

input:

49
YNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN

output:

YES
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

result:

ok OK

Test #25:

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

input:

37
YNYYYYYYYYYNYNNYYNNNYYYNNYNYNYNYYYNNY

output:

YES
1 24 1 1 1 1 1 1 1 1 1 24 1 24 24 1 1 24 24 24 1 1 1 24 24 1 24 1 24 1 24 1 1 1 24 24 1

result:

ok OK

Test #26:

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

input:

4
NYNN

output:

YES
1 4 1 2

result:

ok OK

Test #27:

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

input:

29
NNYNNNNNNNNYNNNNNNNNNNNNNNNNN

output:

YES
1 2 7 4 22 22 22 22 22 22 22 7 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22

result:

ok OK

Test #28:

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

input:

21
YYYYNYYNYYYYYNYNYNYYN

output:

YES
1 1 1 1 16 1 1 16 1 1 1 1 1 16 1 16 1 16 1 1 16

result:

ok OK

Test #29:

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

input:

12
YYYYYNYYYYYY

output:

YES
1 1 1 5 5 2 5 5 5 5 5 5

result:

ok OK

Test #30:

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

input:

14
NYYYYYNYYYYYYY

output:

YES
1 3 3 3 3 3 2 3 3 3 3 3 3 3

result:

ok OK

Test #31:

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

input:

9
YYYYYYNNN

output:

YES
7 7 7 7 7 7 1 2 4

result:

ok OK

Test #32:

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

input:

48
NNNNYYNNYNNNNNNYNNNNNNNNNNYYNNNNNNNYNNNNNNNNNNNN

output:

YES
2 26 26 26 1 1 26 26 1 26 26 26 26 26 26 5 26 26 26 26 26 26 26 26 26 26 5 5 26 26 26 26 26 26 26 5 26 26 26 26 26 26 26 26 26 26 26 26

result:

ok OK

Test #33:

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

input:

12
YYYYNYNYNNNY

output:

YES
1 1 1 5 2 5 26 5 26 26 26 5

result:

ok OK

Test #34:

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

input:

13
NNNNYNYNNNNNN

output:

YES
1 2 4 22 7 22 7 22 22 22 22 22 22

result:

ok OK

Test #35:

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

input:

50
NNNNYYNYYYYNNNNYYNNYYNNNNYNNYYYYNNNNNYYYYNYYNNNYYN

output:

YES
2 106 106 106 1 1 106 1 5 5 5 106 106 106 106 5 5 106 106 5 5 106 106 106 106 5 106 106 5 5 5 5 106 106 106 106 106 5 5 5 5 106 5 5 106 106 106 5 5 106

result:

ok OK

Test #36:

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

input:

30
YNYNNNNYNNYNNYYNYYYYNNYNNYNNNY

output:

YES
1 2 1 56 56 56 56 1 56 56 5 56 56 5 5 56 5 5 5 5 56 56 5 56 56 5 56 56 56 5

result:

ok OK

Test #37:

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

input:

46
NNNNNYNNNNNNYNNNNNNNNNNNNNNNNNYNNNNNNNYNNNNNYN

output:

YES
2 16 16 16 16 1 16 16 16 16 16 16 1 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 1 16 16 16 16 16 16 16 5 16 16 16 16 16 5 16

result:

ok OK

Test #38:

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

input:

16
NYYYYYYNNYYNYYYY

output:

YES
1 3 3 3 3 3 3 2 40 3 3 40 3 3 3 3

result:

ok OK

Test #39:

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

input:

8
YYYNYYYY

output:

YES
1 1 1 2 5 5 5 5

result:

ok OK

Test #40:

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

input:

44
YNYNNNNNNYNNNNYNNNNNNNYNNNYYYYNYNYNNYNNNNNNN

output:

YES
3 1 3 2 40 40 40 40 40 3 40 40 40 40 3 40 40 40 40 40 40 40 3 40 40 40 3 3 3 3 40 3 40 3 40 40 3 40 40 40 40 40 40 40

result:

ok OK

Test #41:

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

input:

42
NYYYYYNNNNNNNNYNNYYYYYYNYYYYYNYYYYYYYNYYNN

output:

YES
1 3 3 3 3 3 2 82 82 82 82 82 82 82 3 82 82 3 3 3 3 3 3 82 3 3 3 3 3 82 3 3 3 3 3 3 3 82 3 3 82 82

result:

ok OK

Test #42:

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

input:

15
NYNNNNYYYNNNYYY

output:

YES
8 1 8 8 8 8 1 1 1 8 8 8 1 1 1

result:

ok OK

Test #43:

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

input:

21
NNNYNYYYYNYYNYYYNYYYY

output:

YES
1 2 4 7 106 7 7 7 7 106 7 7 106 7 7 7 106 7 7 7 7

result:

ok OK

Test #44:

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

input:

23
YYYYYNYNNYNNNNYNYYNNYYN

output:

YES
7 7 7 7 7 1 7 2 4 7 92 92 92 92 7 92 7 7 92 92 7 7 92

result:

ok OK

Test #45:

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

input:

29
YYYYYNNYYYYNNNNYYNNNYYNNYNNNN

output:

YES
7 7 7 7 7 1 2 7 7 7 7 4 106 106 106 7 7 106 106 106 7 7 106 106 7 106 106 106 106

result:

ok OK

Test #46:

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

input:

38
YYNNNYYYNNNYYNNNNNNYNNNNNNYYYYNNNNNNNY

output:

YES
1 1 2 56 56 1 5 5 56 56 56 5 5 56 56 56 56 56 56 5 56 56 56 56 56 56 5 5 5 5 56 56 56 56 56 56 56 5

result:

ok OK

Test #47:

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

input:

4
NYYY

output:

YES
2 1 1 1

result:

ok OK

Test #48:

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

input:

39
NNYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYNYNYYY

output:

YES
1 2 7 7 7 7 7 7 7 4 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 246 7 246 7 7 7

result:

ok OK

Test #49:

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

input:

14
NNNYNNNNNNNNNN

output:

YES
1 1 2 4 9 9 9 9 9 9 9 9 9 9

result:

ok OK

Test #50:

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

input:

48
YNNNNYYYYNYYNNYYYYNNYNNYNYYYYYYNYYYYNNNNYNYNNNNN

output:

YES
1 2 116 116 116 1 1 5 5 116 5 5 116 116 5 5 5 5 116 116 5 116 116 5 116 5 5 5 5 5 5 116 5 5 5 5 116 116 116 116 5 116 5 116 116 116 116 116

result:

ok OK

Test #51:

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

input:

30
NNNNNNNYYNYNNNNYNNNYNNNNYNNNYY

output:

YES
1 2 28 28 28 28 28 3 3 28 3 28 28 28 28 3 28 28 28 3 28 28 28 28 3 28 28 28 3 3

result:

ok OK

Test #52:

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

input:

36
YNYYYYYNYNNNYNYYNYYNYNNYNNYYNNNYYNYN

output:

YES
1 2 1 1 5 5 5 86 5 86 86 86 5 86 5 5 86 5 5 86 5 86 86 5 86 86 5 5 86 86 86 5 5 86 5 86

result:

ok OK

Test #53:

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

input:

26
YNYYYYYYYYYNYYYNYYYYYYYYYY

output:

YES
1 2 1 1 5 5 5 5 5 5 5 106 5 5 5 106 5 5 5 5 5 5 5 5 5 5

result:

ok OK

Test #54:

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

input:

33
YNNYNNNNNYYYYNNNNYYNYNNYNNYNNYNYN

output:

YES
1 14 14 1 14 14 14 14 14 1 1 1 1 14 14 14 14 1 1 14 1 14 14 1 14 14 1 14 14 1 14 1 14

result:

ok OK