oj.uz

Submission #861848

# Submission time Handle Problem Language Result Execution time Memory
861848 2023-10-17T04:36:21 Z iskhakkutbilim parentrises (BOI18_parentrises) C++17
0 / 100
 1 ms 500 KB 
#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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -