QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #294595 | #4824. Bracket-and-bar Sequences | ucup-team1525# | 0 | 0ms | 3916kb | C++20 | 2.4kb | 2023-12-30 14:53:12 | 2023-12-30 14:53:13 |
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=25;
ll f[N+5];
void prep(){
f[0]=1;
for(int i=1;i<=N;i++)
for(int j=0;j<i;j++)
for(int k=0;j+k<i;k++)
f[i]+=f[j]*f[k]*f[i-j-k-1];
// printf("%lld\n",f[N]);
}
ll dfs(int n,char s[N*3+5]){
if(n==0) return 1;
int j=0,k=0,mt=0,cnt=0;
for(int i=0;i<n*3;i++)
if(s[i]=='(') mt++;
else if(s[i]==')'){
mt--;
if(!mt){
k=cnt; break;
}
cnt++;
}
else{
if(mt==1) j=cnt;
}
//printf("%d %d %d\n",n,j,k);
ll res=0;
for(int j1=0;j1<j;j1++)
for(int k1=0;j1+k1<n;k1++)
res+=f[j1]*f[k1]*f[n-1-j1-k1];
for(int k1=0;j+k1<k;k1++)
res+=f[j]*f[k1]*f[n-1-j-k1];
char t[N*3+5];
int lt=0;
for(int i=1;i<=j*3;i++)
t[lt++]=s[i];
for(int i=j*3+2;i<3*k+2;i++)
t[lt++]=s[i];
for(int i=3*k+3;i<3*n;i++)
t[lt++]=s[i];
return res+dfs(n-1,t);
}
void encode(){
int n;
char s[N*3+5];
scanf("%d",&n);
scanf("%s",s);
printf("%lld\n",dfs(n,s));
}
char ans[N*3+5];
void dfs(int n,ll res){
if(n==0) return;
for(int j=0;j<n;j++)
for(int k=0;j+k<n;k++){
ll tmp=f[j]*f[k]*f[n-j-k-1];
if(tmp<res) res-=tmp;
else{
// printf("%d %d %d\n",n,j,k);
dfs(n-1,res);
char now[N+5];
int lt=0;
now[0]='(';
for(int i=1;i<=j*3;i++)
now[i]=ans[lt++];
now[j*3+1]='|';
for(int i=j*3+2;i<3*(j+k)+2;i++)
now[i]=ans[lt++];
now[3*(j+k)+2]=')';
for(int i=3*(j+k)+3;i<3*n;i++)
now[i]=ans[lt++];
for(int i=0;i<3*n;i++)
ans[i]=now[i];
return;
}
}
}
void decode(){
int n; ll res;
scanf("%d",&n);
scanf("%lld",&res);
dfs(n,res);
printf("%s\n",ans);
}
int main(){
prep();
char s[10];
scanf("%s",s);
if(s[0]=='e'){
int t; scanf("%d",&t);
while(t--) encode();
}
else{
int t; scanf("%d",&t);
while(t--) decode();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3916kb
input:
encode 3 1 (|) 4 ((((|)|)|)|) 5 (|(|))((|(|))|)
output:
1 55 66
input:
decode 3 1 1 4 55 5 66
output:
(|) ((((|)|)|)|) (|(|))((|(|))|)
result:
ok 3 lines
Test #2:
score: 100
Accepted
time: 0ms
memory: 3812kb
input:
encode 1 1 (|)
output:
1
input:
decode 1 1 1
output:
(|)
result:
ok single line: '(|)'
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 3860kb
input:
encode 3 2 ((|)|) 1 (|) 2 (|(|))
output:
3 1 2
input:
decode 3 2 3 1 1 2 2
output:
((|)|) (|))|) (|(|))
result:
wrong answer 2nd lines differ - expected: '(|)', found: '(|))|)'