QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#13236 | #1439. Football Match | Qingyu | AC ✓ | 3ms | 3732kb | C++20 | 3.3kb | 2021-08-29 15:12:52 | 2022-05-17 01:39:43 |
Judging History
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