Submission #170740

#	Time	Username	Problem	Language	Result	Execution time	Memory
170740		dndhk	parentrises (BOI18_parentrises)	C++14	16 / 100	4 ms	376 KiB

parentrises

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 1;

int P, T;
string str;
vector<pii> vt;
vector<int> ans;

int main(){
	scanf("%d%d", &P, &T);
	if(P==1){
		while(T--){
			bool tf = true;
			cin>>str;
			if(str[0]==')'){
				printf("impossible\n");
				continue;
			}
			vt.pb({1, 2});
			for(int i=1; i<str.size(); i++){
				pii prv = vt.back();
				if(str[i]=='('){
					prv.first++; prv.second+=2;
				}else{
					prv.first-=2; prv.second--;
				}
				if(prv.second<0){
					tf = false;
					break;
				}
				prv.first = max(prv.first, 0);
				vt.pb(prv);
			}
			if(vt.back().first!=0){
				tf = false;
			}
			if(!tf){
				printf("impossible\n");
			}else{
				int num1=0, num2=0;
				int n = 0;
				for(int i=str.size()-1; i>=0; i--){
					pii now = vt[i]; vt.pop_back();
					if(vt.empty()){
						if(n==2){
							ans.pb(3);
						}else{
							if(num1>0)	ans.pb(1);
							else	ans.pb(2);
						}
					}else{
						if(str[i]=='('){
							if(vt.back().first<=n-1 && n-1<=vt.back().second){
								if(num1<num2){
									ans.pb(2); num2--;
								}else{
									ans.pb(1); num1--;
								}
								n--;
							}else{
								ans.pb(3);
								num1--; num2--;
								n-=2;
							}
						}else{
							if(vt.back().first<=n+1 && n+1<=vt.back().second){
								if(num1>num2){
									ans.pb(2); num2++;
								}else{
									ans.pb(1); num1++;
								}
								n++;
							}else{
								ans.pb(3);
								num1++; num2++;
								n+=2;
							}
						}
					}
				}
				while(!ans.empty()){
					if(ans.back()==3){
						printf("G");
					}else if(ans.back()==2){
						printf("B");
					}else{
						printf("R");
					}
					ans.pop_back();
				}
				printf("\n");
			}
		}
	}else{

	}
	return 0;
}

Compilation message (stderr)

parentrises.cpp: In function 'int main()':
parentrises.cpp:43:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=1; i<str.size(); i++){
                 ~^~~~~~~~~~~
parentrises.cpp:66:10: warning: variable 'now' set but not used [-Wunused-but-set-variable]
      pii now = vt[i]; vt.pop_back();
          ^~~
parentrises.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &P, &T);
  ~~~~~^~~~~~~~~~~~~~~~

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