Submission #62176

#	Time	Username	Problem	Language	Result	Execution time	Memory
62176		gs14004	parentrises (BOI18_parentrises)	C++17	100 / 100	43 ms	6572 KiB

parentrises

#include<bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using lint = long long;
const int MAXN = 1000050;
const int mod = 1e9 + 7;

/*
 * Generator (N^4)
 * Generates ans array in 22min (from my 2015 laptop)
 
int n;
int mem[305][305][2];

int dp(int x1, int x2, int y1, int y2, int numcnt, int curH, int vis){
	if(numcnt < 0 || curH + x1 < 0) return 0;
	if(x2 + y2 == n) return numcnt == 0 && vis && x2 >= x1 && y2 >= y1;
	if(~mem[x2][y2][vis]) return mem[x2][y2][vis];
	int ans = 0;
	if(x2 < x1){
		ans += dp(x1, x2 + 1, y1, y2, numcnt + 2, curH + 1, vis);
	}
	else{
		ans += dp(x1, x2 + 1, y1, y2, numcnt + 1, curH + 1, vis);
	}
	if(y2 < y1){
		ans += dp(x1, x2, y1, y2 + 1, numcnt - 1, curH - 1, vis | ((curH - 1) + x1 == 0));
	}
	else{
		ans += dp(x1, x2, y1, y2 + 1, numcnt - 2, curH - 1, vis | ((curH - 1) + x1 == 0));
	}
	return mem[x2][y2][vis] = ans % mod;
}

int f(int _n){
	n = _n;
	int ans = 0;
	for(int i=0; i<=n; i++){
		for(int j=0; i+j<=n; j++){
			memset(mem, -1, sizeof(mem));
			ans += dp(i, 0, j, 0, 0, 0, i == 0);
			ans %= mod;
		}
	}
	return ans;
}*/

string solve(string s){
	queue<int> que;
	string chk;
	int cnt = 0;
	chk.resize(s.size());
	for(int i=0; i<s.size(); i++){
		if(s[i] == '('){
			que.push(i);
			cnt++;
			chk[i] = '?';
		}
		else{
			if(cnt > 0){
				chk[i] = '!';
				cnt--;
			}
			else{
				if(que.empty()) return "impossible";
				int x = que.front();
				que.pop();
				chk[x] = 'G';
				chk[i] = '!';
			}
		}
	}
	for(int i=(int)s.size()-1; i>=0; i--){
		if(s[i] == ')' && cnt){
			chk[i] = 'G';
			cnt--;
		}
	}
	if(cnt > 0) return "impossible";
	int c0 = 0, c1 = 0;
	for(int i=0; i<s.size(); i++){
		if(s[i] == '('){
			if(chk[i] == 'G') cnt += 2;
			else{
				cnt++;
				if(cnt & 1) chk[i] = 'R';
				else chk[i] = 'B';
			}
			if(chk[i] != 'B') c0++;
			if(chk[i] != 'R') c1++;
		}
		else{
			if(chk[i] == 'G') cnt -= 2;
			else{
				if(cnt & 1) chk[i] = 'R';
				else chk[i] = 'B';
				cnt--;
			}
			if(chk[i] != 'B') c0--;
			if(chk[i] != 'R') c1--;
		}
		if(c0 < 0 || c1 < 0) return "impossible";
	}
	if(c0 == 0 && c1 == 0) return chk;
	else return "impossible";
}

int ans[305] = {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};

int main(){
	char buf[MAXN];
	int p, t; cin >> p;
	if(p == 1){
		scanf("%d",&t);
		while(t--){
			scanf("%s",buf);
			string ans = buf;
			printf("%s\n", solve(buf).c_str());
		}
	}
	else{
		scanf("%d",&t);
		while(t--){
			int x; cin >> x; cout << ans[x-1] << endl;
		}
	}
}

Compilation message (stderr)

parentrises.cpp: In function 'std::__cxx11::string solve(std::__cxx11::string)':
parentrises.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<s.size(); i++){
               ~^~~~~~~~~
parentrises.cpp:81:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<s.size(); i++){
               ~^~~~~~~~~
parentrises.cpp: In function 'int main()':
parentrises.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t);
   ~~~~~^~~~~~~~~
parentrises.cpp:116:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s",buf);
    ~~~~~^~~~~~~~~~
parentrises.cpp:122:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t);
   ~~~~~^~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 6 / 6
• Subtask 4: 28 / 28
• Subtask 5: 6 / 6
• Subtask 6: 16 / 16
• Subtask 7: 28 / 28