QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#618170	#4824. Bracket-and-bar Sequences	lichenyu_ac	0	2ms	3992kb	C++14	1.8kb	2024-10-06 19:32:04	2024-10-06 19:32:05

Judging History

你现在查看的是最新测评结果

[2024-10-06 19:32:05]
评测

测评结果：0
用时：2ms
内存：3992kb

查看

[2024-10-06 19:32:04]
提交

answer

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=110;

namespace encode{

	ll f[N];
	int n;
	string s;

	ll solve(int n,string s){
		if(!n)return 0;
		int l=0,mid=0,r=0;
		int top=0;
		for(int i=0;;i++){
			top+=s[i]=='(',top-=s[i]==')';
			if(top==1&&s[i]=='|')mid=i;
			if(!top){
				r=i;
				break;
			}
		}
		int cnt1=(mid-l-1)/3,cnt2=(r-mid-1)/3,cnt3=(n*3-r-1)/3;
		ll val=0;
		for(int i=0;i<n;i++)
			for(int j=0;i+j<n;j++)
				if(i==cnt1&&j==cnt2)
					return val+solve(cnt1,s.substr(1,cnt1*3))*f[cnt2]+solve(cnt2,s.substr(mid+1,cnt2*3))*f[cnt3]+solve(cnt3,s.substr(r+1,cnt3*3));
				else val+=f[i]*f[j]*f[n-1-i-j];
		return -1;
	}

	void solve(){
		cin>>n>>s;
		printf("%lld\n",solve(n,s));
	}

	int main(){
		f[0]=1;
		for(int i=1;i<=25;i++)
			for(int j=0;j<i;j++)
				for(int k=0;j+k<i;k++)
					f[i]+=f[j]*f[k]*f[i-1-j-k];
		int T;
		cin>>T;
		while(T--)solve();
		return 0;
	}
}

namespace decode{

	ll f[N];
	int n;
	string s;

	string solve(int n,ll s){
		if(!n)return "";
		for(int i=0;i<n;i++)
			for(int j=0;i+j<n;j++)
				if(s<f[i]*f[j]*f[n-1-i-j]){
					ll s3=s%f[n-1-i-j];
					ll s2=(s/f[n-1-i-j])%f[j];
					ll s1=s/f[n-1-i-j]/f[j];
					return "("+solve(i,s1)+"|"+solve(j,s2)+")"+solve(n-1-i-j,s3);
				}else s-=f[i]*f[j]*f[n-1-i-j];
		return "-1";
	}

	void solve(){
		int n;ll s;
		cin>>n>>s;
		cout<<solve(n,s)<<endl;
	}

	int main(){
		f[0]=1;
		for(int i=1;i<=25;i++)
			for(int j=0;j<i;j++)
				for(int k=0;j+k<i;k++)
					f[i]+=f[j]*f[k]*f[i-1-j-k];
		int T;
		cin>>T;
		while(T--)solve();
		return 0;
	}
}

int main(){
    // freopen("test.in","r",stdin);
    // freopen("test.out","w",stdout);
    string s;
    cin>>s;
    if(s=="encode")encode::main();
    else decode::main();
    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3736kb

input:

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

output:

0
54
65

input:

decode
3
1
0
4
54
5
65

output:

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

result:

ok 3 lines

Test #2:

score: 100

Accepted

time: 0ms

memory: 3956kb

input:

encode
1
1
(|)

output:

input:

decode
1
1
0

output:

(|)

result:

ok single line: '(|)'

Test #3:

score: 100

Accepted

time: 0ms

memory: 3992kb

input:

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

output:

2
0
1

input:

decode
3
2
2
1
0
2
1

output:

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

result:

ok 3 lines

Test #4:

score: 0

Wrong Answer

time: 2ms

memory: 3716kb

input:

encode
1000
3
(|)(|)(|)
3
(|)(|(|))
3
(|)((|)|)
3
(|(|))(|)
3
(|(|)(|))
3
(|(|(|)))
3
(|((|)|))
3
((|)|)(|)
3
((|)|(|))
3
((|)(|)|)
3
((|(|))|)
3
(((|)|)|)
4
(|)(|)(|)(|)
4
(|)(|)(|(|))
4
(|)(|)((|)|)
4
(|)(|(|))(|)
4
(|)(|(|)(|))
4
(|)(|(|(|)))
4
(|)(|((|)|))
4
(|)((|)|)(|)
4
(|)((|)|(|))
4
(|)((|)...

output:

input:

output:

(|)(|)(|)
(|)(|(|))
(|)((|)|)
(|(|))(|)
(|(|)(|))
(|(|(|)))
(|((|)|))
((|)|)(|)
((|)|(|))
((|)(|)|)
((|(|))|)
(((|)|)|)
(|)(|)(|)(|)
(|)(|)(|(|))
(|)(|)((|)|)
(|)(|(|))(|)
(|)(|(|)(|))
(|)(|(|(|)))
(|)(|((|)|))
(|)((|)|)(|)
(|)((|)|(|))
(|)((|)(|)|)
(|)((|(|))|)
(|)(((|)|)|)
(|(|))(|)(|)
(|(|))(|(|)...

result:

wrong answer 244th lines differ - expected: '((|(|))|)(|)(|)', found: '((|)(|)|)(|(|))'