QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #301119 | #4824. Bracket-and-bar Sequences | daniel14311531 | 0 | 0ms | 3604kb | C++14 | 2.4kb | 2024-01-09 14:48:26 | 2024-01-09 14:48:26 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 110;
ll f[N], g[N];
namespace ENCODE {
int n;
string s;
int rb[N], pos[N];
void init() {
int sta[N], top; top = 0;
for(int i = 0; i < 3 * n; i++) {
if(s[i] == '(') sta[++top] = i;
else if(s[i] == ')') rb[sta[top]] = i, --top;
else pos[sta[top]] = i;
}
}
ll dfs(int l, int r) {
if(l > r) return 1;
int p = pos[l], q = rb[l];
int cntl = (p - l - 1) / 3, cntr = (q - p - 1) / 3;
int cl = (q - l + 1) / 3, cr = (r - q) / 3;
ll res = 0;
for(int i = 1; i < cl; i++) {
res += f[i] * g[cl + cr - i];
}
for(int i = 0; i < cntl; i++) {
res += g[(r - q) / 3] * g[i] * g[cntl + cntr - i];
}
res += ((dfs(l + 1, p - 1) - 1) * g[cntr] + dfs(p + 1, q - 1) - 1) * g[cr];
return res + dfs(q + 1, r);
}
void MAIN() {
int T; cin >> T;
for(; T; --T) {
cin >> n;
cin >> s;
init();
cout << dfs(0, 3 * n - 1) << "\n";
}
}
}
namespace DECODE {
int n; ll m;
string s;
void dfs(int l, int r, ll rem) {
cout << ">>> dfs : " << l << " " << r << " " << rem << "\n";
if(l > r) return ;
int p, q;
int cntl, cntr, cl, cr;
cl = 1;
for(int i = 1;; i++) {
ll tmp = f[i] * g[(r - l + 1) / 3 - i];
if(tmp >= rem) {
cl = i, cr = (r - l + 1) / 3 - cl;
q = l + cl * 3 - 1;
break;
}
rem -= tmp;
}
s[l] = '(', s[q] = ')';
cntl = 0;
for(int i = 0;; i++) {
ll tmp = g[(r - q) / 3] * g[i] * g[(q - l - 2) / 3 - i];
if(tmp >= rem) {
cntl = i, cntr = (q - l - 2) / 3 - cntl;
p = cntl * 3 + l + 1;
break;
}
rem -= tmp;
}
s[p] = '|';
dfs(q + 1, r, (rem - 1) % g[cr] + 1);
rem = (rem - 1) / g[cr] + 1;
dfs(p + 1, q - 1, (rem - 1) % g[cntr] + 1);
rem = (rem - 1) / g[cntr] + 1;
dfs(l + 1, p - 1, rem);
}
void MAIN() {
int T; cin >> T;
for(; T; --T) {
cin >> n, cin >> m;
s.resize(3 * n);
dfs(0, 3 * n - 1, m);
cout << s << "\n";
}
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(nullptr);
f[0] = f[1] = 1;
g[0] = g[1] = 1;
for(int i = 2; i <= 25; i++) {
for(int j = 0; j < i; j++)
f[i] = f[i] + g[j] * g[i - 1 - j];
for(int j = 0; j < i; j++) {
g[i] = g[i] + g[j] * f[i - j];
}
}
// cout << g[25] << "\n";
string op; cin >> op;
if(op == "encode") ENCODE::MAIN();
else DECODE::MAIN();
return 0;
}
/*
decode
3
1
1
4
55
5
66
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3604kb
input:
encode 3 1 (|) 4 ((((|)|)|)|) 5 (|(|))((|(|))|)
output:
1 55 66
input:
decode 3 1 1 4 55 5 66
output:
>>> dfs : 0 2 1 >>> dfs : 3 2 1 >>> dfs : 2 1 1 >>> dfs : 1 0 1 (|) >>> dfs : 0 11 55 >>> dfs : 12 11 1 >>> dfs : 11 10 1 >>> dfs : 1 9 12 >>> dfs : 10 9 1 >>> dfs : 9 8 1 >>> dfs : 2 7 3 >>> dfs : 8 7 1 >>> dfs : 7 6 1 >>> dfs : 3 5 1 >>> dfs : 6 5 1 >>> dfs : 5 4 1 >>> dfs : 4 3 1 ((((|)|)|)|) >>>...
result:
wrong answer 1st lines differ - expected: '(|)', found: '>>> dfs : 0 2 1'