Submission #861848

#	Time	Username	Problem	Language	Result	Execution time	Memory
861848		iskhakkutbilim	parentrises (BOI18_parentrises)	C++17	0 / 100	1 ms	500 KiB

parentrises

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

#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int mod = 1e9 + 7;

int P;
int see[3][3];

void solve(){
	string s; cin >> s;
	int n = s.size();
	vector<vector<int>> dp(n, vector<int>(3, 0));
	vector<vector<pair<int, int> >> parent(n, vector<pair<int, int> >(3, {-1, -1}));
	// RBG
	if(s[0] == ')' or s[n-1] == '('){
		cout << "impossible";
		return;
	}
	dp[0][0] = 1, dp[0][1] = 1, dp[0][2] = 1;
	for(int i = 1;i < n; i++){
		for(int j = 0;j < 3; j++){
			if(s[i] == ')'){
				for(int idx = 0; idx < i; idx++){
					if(s[idx] == ')') continue;
					for(int k = 0;k < 3; k++){
						if(see[k][j]){
							if(dp[idx][k]){
								dp[i][j] = 1;
								parent[i][j] = {idx, k};
							}
						}
					}
				}
			}else{
				for(int k = 0; k < 3; k++){
					if(dp[i-1][k]){
						dp[i][j] = 1;
						parent[i][j] = {i-1, k};
					}
				}
			}
		}
	}
	
	int possible = 0;
	for(int j = 0;j < 3; j++){
		possible|= dp[n-1][j];
	}
	cout << possible;
}


main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
   see[0][0] = 1;
   see[1][1] = 1;
   see[2][2] = 1;
   see[0][2] = see[2][0] = 1;
   see[1][2] = see[2][1] = 1;
   cin >> P;
	int test; cin >> test;
	while(test--){
		solve();
		cout << '\n';
	}
	return 0;
}

Compilation message (stderr)

parentrises.cpp:57:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 | main(){
      | ^~~~

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