QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#460760 | #5534. Match | fryan | 0 | 21ms | 6716kb | C++20 | 2.1kb | 2024-07-02 08:08:18 | 2024-07-02 08:08:18 |
Judging History
answer
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
#define int long long
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
const int mxn = 1e5;
const int mod = 998244353;
const int p = 53;
int ksm(int a, int b=mod-2) {
int res=1, aux=a;
for (int i=1; i<=b; i*=2) {
if (b&i) res = res*aux%mod;
aux = aux*aux%mod;
}
return res;
}
int n, s[mxn], pw[2*mxn], ip[2*mxn], hv[mxn+2];
vector<int> stk;
map<array<int,2>,vector<int>> ep;
vector<int> solve(int l, int r) {
if (l+1 == r) {
assert(s[l] == s[r]);
return {0,1};
}
int f = s[l];
int h = hv[l];
array<int,2> k = {f,h};
auto it = upper_bound(all(ep[k]),r);
--it;
int rb = *it;
vector<int> res = {0};
if (l+1 < rb) {
vector<int> r1 = solve(l+1,rb-1);
for (auto i : r1) {
res.push_back(i);
}
}
res.push_back(1);
if (rb < r) {
vector<int> r1 = solve(rb+1,r);
for (auto i : r1) {
res.push_back(i);
}
}
return {res};
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
//precompute
pw[0] = 1, ip[0] = 1;
for (int i=1; i<2*mxn; i++) {
pw[i] = p*pw[i-1]%mod;
ip[i] = ksm(p)*ip[i-1]%mod;
}
string ss; cin >> ss;
n = sz(ss);
for (int i=0; i<n; i++) {
s[i] = ss[i]-'a'+1;
}
int cv=0;
for (int i=0; i<n; i++) {
hv[i] = cv;
if (i && stk[sz(stk)-1]==s[i]) {
cv -= stk[sz(stk)-1];
cv = cv * ip[1] % mod;
} else {
stk.push_back(s[i]);
cv = (cv * pw[1] + s[i])%mod;
}
}
hv[n]=cv;
if (cv) {
cout<<-1; return 0;
}
for (int i=1; i<=n; i++) {
if (!ep.count({s[i-1],hv[i]})) {
ep[{s[i-1],hv[i]}] = {};
}
ep[{s[i-1],hv[i]}].push_back(i-1);
}
vector<int> ans = solve(0,n-1);
for (auto i: ans) {
cout << (i ? ")" : "(");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 20ms
memory: 6716kb
input:
abbaaa
output:
(()())
result:
ok single line: '(()())'
Test #2:
score: 0
Wrong Answer
time: 21ms
memory: 6596kb
input:
cbbbbccbbccbbbbbbc
output:
-1
result:
wrong answer 1st lines differ - expected: '(((((((()))())))))', found: '-1'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%