QOJ.ac

QOJ

The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#296665	#4824. Bracket-and-bar Sequences	defyers^#	0	0ms	3800kb	C++17	1.9kb	2024-01-03 12:55:46	2024-01-03 12:55:46

Judging History

This is the latest submission verdict.

[2024-01-03 12:55:46]
Judged

Verdict: 0
Time: 0ms
Memory: 3800kb

Show

[2024-01-03 12:55:46]
Submitted

answer

#include "bits/stdc++.h"
#define all(a) begin(a), end(a)
using namespace std;

#define int long long 
using ll = long long;
using pii = pair<int, int>;

int n;

const int N = 26;
int dp[N][N][N];
int prefix(string s){
	int a0, a1, a2;
	a0 = count(all(s), '(');
	a1 = count(all(s), '|');
	a2 = count(all(s), ')');
#ifdef LOCAL
	printf("dp[%lld][%lld][%lld] = %lld\n", a0, a1, a2, dp[a0][a1][a2]);
#endif
	return dp[a0][a1][a2];
}

bool valid(int i, int j, int k){
	return i >= j && j >= k;
}

void precalc(){
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= n; j++){
			for(int k = 0; k <= n; k++){
				dp[i][j][k] = 0;
			}
		}
	}
	dp[n][n][n] = 1;
	for(int i = n; i >= 0; i--){
		for(int j = n; j >= 0; j--){
			for(int k = n; k >= 0; k--){
				if(i * j * k == n * n * n || !valid(i, j, k)) continue;
				if(i < n && valid(i + 1, j, k))
					dp[i][j][k] += dp[i + 1][j][k];
				if(j < n && valid(i, j + 1, k))
					dp[i][j][k] += dp[i][j + 1][k];
				if(k < n && valid(i, j, k + 1))
					dp[i][j][k] += dp[i][j][k + 1];
			}
		}
	}
}

void encode() {
	cin >> n;
	precalc();
	string s; cin >> s;
	int cnt = 0;
	for(int i = 0; i < n * 3; i++){
		if(s[i] == '|' || s[i] == ')') cnt += prefix(s.substr(0, i) + "(");
		if(s[i] == ')') cnt += prefix(s.substr(0, i) + "|");
	}
	cout << cnt << '\n';
}

void decode() {
	cin >> n;
	precalc();
	int cnt; cin >> cnt;
	string ans;
	for(int i = 0; i < n * 3; i++){
		int s = prefix(ans + "(");
		if(cnt < s){
			ans.push_back('('); continue;
		}
		cnt -= s;

		s = prefix(ans + "|");
		if(cnt < s){
			ans.push_back('|'); continue;
		}
		cnt -= s;
		
		ans.push_back(')');
	}
	cout << ans << '\n';
}
 
int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cout << fixed << setprecision(10);

	string type; cin >> type;
	int t; cin >> t;

	while(t--){
		if(type == "encode") encode();
		else decode();
	}
	
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3800kb

input:

encode
3
1
(|)
4
((((|)|)|)|)
5
(|(|))((|(|))|)

output:

0
13
5047

input:

decode
3
1
0
4
13
5
5047

output:

(|)
((((|)|)|)|)
(|(|))((|(|))|)

result:

ok 3 lines

Test #2:

score: 100

Accepted

time: 0ms

memory: 3616kb

input:

encode
1
1
(|)

output:

input:

decode
1
1
0

output:

(|)

result:

ok single line: '(|)'

Test #3:

score: 0

Wrong Answer

time: 0ms

memory: 3620kb

input:

encode
3
2
((|)|)
1
(|)
2
(|(|))

output:

1
4
2

input:

decode
3
2
1
1
4
2
2

output:

((|)|)
)))
(|(|))

result:

wrong answer 2nd lines differ - expected: '(|)', found: ')))'