Submission #65171

#	Time	Username	Problem	Language	Result	Execution time	Memory
65171		spencercompton	parentrises (BOI18_parentrises)	C++14	50 / 100	216 ms	11540 KiB

parentrises

#include <bits/stdc++.h>
using namespace std;


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int p, cases;
	cin >> p >> cases;
	if(p==1){
		for(int z = 1; z<=cases; z++){
			string s;
			cin >> s;
			bool pos = true;
			int open = 0;
			int close = 0;
			for(int i = 0; i<s.length(); i++){
				if(s[i]=='('){
					open++;
				}
				else{
					close++;
				}
				if(close>2*open){
					pos = false;
				}
			}
			open = 0;
			close = 0;
			for(int i = s.length()-1; i>=0; i--){
				if(s[i]=='('){
					open++;
				}
				else{
					close++;
				}
				if(open > 2*close){
					pos = false;
				}
			}
			int n = (int)s.length();
			int color[n];
			//G = 0, B = 1, R = 2
			for(int i = 0; i<n; i++){
				color[i] = 0;
			}
			open = 0;
			close = 0;
			vector<int> op;
			vector<int> cl;
			bool ok = true;
			vector<int> op2;
			vector<int> cl2;
			int point = 0;
			for(int i = 0; i<n; i++){
				if(s[i]=='('){
					op.push_back(i);
					open++;
				}
				else{
					cl.push_back(i);
					close++;
					if(close>open){
						if(point+2 > cl.size()){
							ok = false;
							break;
						}
						cl2.push_back(cl[point++]);
						cl2.push_back(cl[point++]);
						close--;
					}
				}
			}
			int dif = open-close;
			if(!ok || 2*dif>open){
				assert(!pos);
				cout << "impossible" << endl;
				continue;
			}
			for(int i = 0; i<2*dif; i++){
				op2.push_back(op.back());
				op.pop_back();
			}
			assert(op2.size()%2==0 && cl2.size()%2==0);
			for(int i = 0; i<op2.size(); i+=2){
				color[op2[i]] = 1;
				color[op2[i+1]] = 2;
			}
			for(int i = 0; i<cl2.size(); i+=2){
				color[cl2[i]] = 1;
				color[cl2[i+1]] = 2;
			}
			int bal1 = 0;
			int bal2 = 0;
			for(int i = 0; i<n; i++){
				if(color[i]==0 || color[i]==1){
					if(s[i]=='('){
						bal1++;
					}
					else{
						bal1--;
					}
				}
				if(color[i]==0 || color[i]==2){
					if(s[i]=='('){
						bal2++;
					}
					else{
						bal2--;
					}
				}
				if(bal1<0 || bal2<0){
					ok = false;
				}
			}
			ok &= bal1==0 && bal2==0;
			if(!ok){
				assert(!pos);
				cout << "impossible" << endl;
				continue;
			}
			assert(ok);
			for(int i = 0; i<n; i++){
				if(color[i]==0){
					cout << "G";
				}
				else if(color[i]==1){
					cout << "B";
				}
				else{
					cout << "R";
				}
			}
			cout << endl;
		}
	}
	else{
		assert(false);
	}
}

Compilation message (stderr)

parentrises.cpp: In function 'int main()':
parentrises.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i<s.length(); i++){
                   ~^~~~~~~~~~~
parentrises.cpp:64:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(point+2 > cl.size()){
          ~~~~~~~~^~~~~~~~~~~
parentrises.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i<op2.size(); i+=2){
                   ~^~~~~~~~~~~
parentrises.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i<cl2.size(); i+=2){
                   ~^~~~~~~~~~~

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