Submission #65162

#	Time	Username	Problem	Language	Result	Execution time	Memory
65162		Mamnoon_Siam	parentrises (BOI18_parentrises)	C++17	50 / 100	192 ms	20044 KiB

parentrises

//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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

#define debug(s) cout << #s << " = " << s << endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a, val) memset(a, val, sizeof (a))
#define PB push_back
#define endl '\n'
typedef long long ll;

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}

template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
	return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;

template<typename T> using min_pq =
	std::priority_queue<T, vector<T>, greater<T> >;

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

const int maxn = 1000006;

int matched[maxn], wot[maxn];
string s;

int32_t main () {
	// freopen("in", "r", stdin);
	int p; cin >> p;
	int t; cin >> t;
	while(t--) {
	    cin >> s;
	    for(int i = 0; i < s.size(); i++)
	    	matched[i] = 0, wot[i] = 0;
	    stack<int> stk;
	    for(int i = 0; i < s.size(); i++) {
	    	if(s[i] == '(') stk.emplace(i);
	    	if(s[i] == ')') {
	    		if(stk.size()) {
	    			int top = stk.top();
	    			matched[top] = 1;
	    			matched[i] = 1;
	    			wot[top]++;
	    			wot[i]++;
	    			stk.pop();
	    		}
	    	}
	    }
	    int flag = 1;
	    while(stk.size()) stk.pop();
	    for(int i = 0; i < s.size(); i++) {
	    	if(matched[i] and s[i] == '(') {
	    		stk.emplace(i);
	    	}
	    	if(!matched[i] and s[i] == ')') {
	    		if(stk.size()) {
	    			int top = stk.top();
	    			stk.pop();
	    			wot[top] += 2;
	    			matched[i] = 1;
	    			wot[i] += 2;
	    		} else {
	    			flag = 0;
	    			break;
	    		}
	    	}
	    }
	    while(stk.size()) stk.pop();
	    for(int i = s.size() - 1; i >= 0; i--) {
	    	if(matched[i] and s[i] == ')') {
	    		stk.emplace(i);
	    	}
	    	if(!matched[i] and s[i] == '(') {
	    		if(stk.size()) {
	    			int top = stk.top();
	    			stk.pop();
	    			wot[top] += 2;
	    			matched[i] = 1;
	    			wot[i] += 2;
	    		} else {
	    			flag = 0;
	    			break;
	    		}
	    	}
	    }
	    if(!flag) {
	    	cout << "impossible" << endl;
	    } else {
	    	string ans;
	    	for(int i = 0; i < s.size(); i++) {
	    		if(wot[i] == 1) ans += "R";
	    		else if(wot[i] == 2) ans += "B";
	    		else ans += "G";
	    	}
	    	cout << ans << endl;
	    }
	}
}

Compilation message (stderr)

parentrises.cpp: In function 'int myrand(int, int)':
parentrises.cpp:18:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
parentrises.cpp:18:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~
parentrises.cpp: In function 'int32_t main()':
parentrises.cpp:45:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i = 0; i < s.size(); i++)
                     ~~^~~~~~~~~~
parentrises.cpp:48:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i = 0; i < s.size(); i++) {
                     ~~^~~~~~~~~~
parentrises.cpp:63:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i = 0; i < s.size(); i++) {
                     ~~^~~~~~~~~~
parentrises.cpp:102:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < s.size(); i++) {
                      ~~^~~~~~~~~~

• 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