| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 61887 |
2018-07-27T04:25:33 Z |
ainta(#1792) |
parentrises (BOI18_parentrises) |
C++11 |
|
3 ms |
564 KB |
#include<cstdio>
#include<algorithm>
#include<queue>
#define N_ 1010000
using namespace std;
char p[N_];
int n, S[N_], v[N_];
int RR[310] = { 0,0,1,2,2,6,12,18,43,86,148,326,652,1194,2531,5062,9578,19884,39768,76680,157236,314472,613440,1248198,2496396,4906266,9932707,19865414,39237478,79165646,158331292,313801154,631634323,263268639,509707998,43257469,86514938,72895660,288290012,576580024,551498904,962513721,925027435,204521844,634307677,268615347,287719520,559111350,118222693,578936427,105459291,210918582,360752402,920849461,841698915,421349166,985137176,970274345,96196738,666703791,333407575,448451120,71192847,142385694,391328273,82210164,164420328,697441626,75399225,150798450,177655189,77725370,155450740,578770998,806452500,612904993,342317187,437431531,874863062,166780006,649351541,298703075,764861307,105948983,211897966,169754380,332500687,665001374,648783808,296688714,593377428,43060831,684124175,368248343,973819030,849070862,698141717,982308804,88186365,176372730,959772055,320975583,641951166,825442333,311190079,622380158,765671696,14446067,28892134,262223145,966556598,933113189,520941027,287565710,575131420,666019185,263936054,527872108,39283492,877846547,755693087,433079969,737806887,475613767,203965075,701508060,403016113,922600280,277710517,555421034,408729101,377397802,754795604,250532053,528340400,56680793,124734442,232656836,465313672,714603167,631625056,263250105,52648990,389536240,779072480,641256163,302398795,604797590,697370162,632833340,265666673,626109777,298187773,596375546,406717000,515830626,31661245,524137426,667633864,335267721,338047842,390892123,781784246,93415445,65330389,130660778,151215664,822766849,645533691,833650616,380489231,760978462,54775313,491923347,983846694,322809267,940997512,881995017,596258099,507985218,15970429,557503950,859869218,719738429,474482700,767988978,535977949,635491203,387005395,774010790,702061186,253594815,507189630,31838831,822372294,644744581,231777149,215914547,431829094,482869402,576014681,152029355,369499245,244741222,489482444,95772722,952809165,905618323,304323137,304632041,609264082,102336119,335070266,670140532,858231094,960619772,921239537,859847032,56893721,113787442,360033502,982628521,965257035,849451750,439416129,878832258,991939394,464496385,928992770,267785589,802816545,605633083,763528731,474974661,949949322,864267253,946087508,892175009,476000768,273171027,546342054,550581443,469352643,938705286,624000951,673806443,347612879,434823692,233016716,466033432,103642988,440059594,880119188,788176043,40656596,81313192,286602731,202636014,405272028,733717711,472596468,945192936,553096598,892385168,784770329,912447619,707646096,415292185,526477156,861291715,722583423,111861393,588150125,176300243,301383510,244253166,488506332,629844702,421869639,843739278,290375226,384946885,769893770,95673275,473895679,947791358,891751001,164209639,328419278,62075416,175112411,350224822,934621064,806088783,612177559,897003764,948394637,896789267,953901352,418921686,837843372 };
void Do1() {
int i;
S[0] = 0;
for (i = 0; i < n; i++) {
if (p[i] == '(')S[i + 1] = S[i] + 1;
else S[i + 1] = S[i] - 1;
}
int Mn = 0;
for (i = 1; i <= n; i++) {
if (Mn > S[i]) {
Mn = S[i];
v[i-1] = 1;
}
}
int t = S[n] - Mn;
for (i = n - 1; i >= 0 && t; i--) {
if (p[i] == '(') {
t--;
v[i] = 1;
}
}
}
bool Do2() {
int i;
queue<int>Q;
int s = 0;
for (i = 0; i < n; i++) {
if (p[i] == '(')s++;
if (p[i] == ')')s--;
if (!v[i] && p[i] == ')') {
Q.push(i);
}
if (s < 0) {
if (Q.empty())return false;
v[Q.front()] = 2;
Q.pop();
s++;
}
}
for (i = n - 1; i >= 0 && s; i--) {
if (!v[i] && p[i] == '(') {
s--;
v[i] = 2;
}
}
int ss = 0;
for (i = 0; i < n; i++) {
if (v[i] != 2) {
if (p[i] == '(')ss++;
else ss--;
}
if (ss < 0)return false;
}
if (ss)return false;
return true;
}
void Solve1() {
int TC, i;
scanf("%d", &TC);
while (TC--) {
scanf("%s", p);
for (i = 0; p[i]; i++)v[i] = 0;
n = i;
Do1();
if (Do2()) {
for (i = 0; i < n; i++) {
if (v[i] == 1)printf("R");
else if (v[i] == 2)printf("B");
else printf("G");
}
printf("\n");
}
else {
puts("impossible");
}
}
}
int Calc(int n) {
return RR[n];
}
void Solve2() {
int i, TC, n;
scanf("%d", &TC);
while (TC--) {
scanf("%d", &n);
printf("%d\n", Calc(n));
}
}
int main() {
//freopen("input.txt", "r", stdin);
int ck;
scanf("%d", &ck);
if (ck == 1) {
Solve1();
}
else {
Solve2();
}
}
Compilation message
parentrises.cpp: In function 'void Solve2()':
parentrises.cpp:90:6: warning: unused variable 'i' [-Wunused-variable]
int i, TC, n;
^
parentrises.cpp: In function 'void Solve1()':
parentrises.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &TC);
~~~~~^~~~~~~~~~~
parentrises.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", p);
~~~~~^~~~~~~~~
parentrises.cpp: In function 'void Solve2()':
parentrises.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &TC);
~~~~~^~~~~~~~~~~
parentrises.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
parentrises.cpp: In function 'int main()':
parentrises.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &ck);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
488 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
488 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
488 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
488 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
488 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
488 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
488 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
564 KB |
Output is correct |
| 2 |
Correct |
3 ms |
564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
564 KB |
Output is correct |
| 2 |
Correct |
3 ms |
564 KB |
Output is correct |
| 3 |
Correct |
3 ms |
564 KB |
Output is correct |
