QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#460762 | #5534. Match | fryan | 37 | 1252ms | 22928kb | C++20 | 2.2kb | 2024-07-02 08:11:47 | 2024-07-02 08:11:48 |
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 = 10;
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;
stk.pop_back();
} 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;
}
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 23ms
memory: 6952kb
input:
abbaaa
output:
(()())
result:
ok single line: '(()())'
Test #2:
score: 0
Accepted
time: 23ms
memory: 6760kb
input:
cbbbbccbbccbbbbbbc
output:
(((((((()))())))))
result:
ok single line: '(((((((()))())))))'
Test #3:
score: 0
Accepted
time: 24ms
memory: 7112kb
input:
ddbcbdacccbddaba
output:
-1
result:
ok single line: '-1'
Subtask #2:
score: 27
Accepted
Dependency #1:
100%
Accepted
Test #4:
score: 27
Accepted
time: 24ms
memory: 8120kb
input:
fsooskkkksokkkkossskkiffoofooikkiiiiiooikkkksookkiissiooookskffsskiiksskiikfiifkifofssooffffkfiiiifkfsiisfsofossiffissikskiikkkiikokikkffkiiksffkkiossifkiookioffoikkkoiiiooioiffkkkssfoooiiiioioskksisikkkoifiooikkkkfiffississkskiofffiffiiiosksskfffofisksksskiisikkskkkksoosiffoofoiooioooifiifssfffffoi...
output:
((((((())))(()))(((()(((()((((()(()))))((((((()((((())(())((((((((())))(()))()))((((((()((()(((()))))(())))((((((())))(((((((()())(((((())())(()()((()(((((((((()))()))(()())))()())())(()(()))))(()))))()))(((())(())))())())())))))())(()())))(())()))))))((())())))))))))(()))))())((())()))(())))((())((...
result:
ok single line: '((((((())))(()))(((()(((()((((...))(())(()))(())())))))))((())))'
Test #5:
score: 0
Accepted
time: 20ms
memory: 6984kb
input:
vvrookjqmmooqlfhnnhflrcbxuuxftajjcqdppoowsswniwsswzzvvisqqbxqniinqeeeaanojvhhttviezzxujjuxyyektlltkoouwwukcqqcifommxxorrnnfgzzyggygvzzvgtxqqxkkummpssllpubbssuubddbebttkkblzzofmmyooyfoqqlpnzznppmvbnnlrrqqlwwbeiievxcnnwppweasjhcchjcarobbogljjlqqgznffmlfabjpiipepummubbbbggzzpjjvvejvgmmqrrkffkqgefrrdbbd...
output:
()(()(((()())(((())))((((())(((()(((((()(())(((())()())(()((((()))(()()((((()(((((()((()))())((())(()(()))(())(((()())()())(()(())((()))((())()(()(()())(()()))(())((()())(()((()(())))())((())()(((()(()())())(()))((()(())(((((()))((((())((())()(((()(((((((())(((())(())()())()()))((()(()(())))((()(())...
result:
ok single line: '()(()(((()())(((())))((((())((...()(()(()))))(())()))(()()()))))'
Test #6:
score: 0
Accepted
time: 24ms
memory: 7996kb
input:
uuueeeuuueeueeeeeeeuueueueeuuuuueeeueeeeeueueueuueuueeueuuuuuuueueueeuueeueeuueeueuueeeueuueeeueueueuueuuueeeeueuuuuueuueueueuuueuuueeeeuueeueeeeeuuuueeeeeuuuueeuuuueueeueuueuuueeeeuueueueueeeeeeeuueueuuueuuuueueeuuueuuuueuuueeuueeeeueeuueuuuuuuuuueeeueuuueueeueeeeuueeuuuueuueeuuueuueeuuueeueeuueueu...
output:
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...
result:
ok single line: '((((((((((((((((((((((((((((((...)))))))))))))))))))))))))))))))'
Test #7:
score: 0
Accepted
time: 24ms
memory: 6976kb
input:
qeeqqqeeqqqquqeeeequuquuuqqqeqqqeeqquqqeeeuuueqqeeqqqqqeeeeeeeeeuqeqquuueeuqeqeqqueeuuuueeeeuuuqqquueuqeeeqeeeqeeqeqqequeeueqquuquqququqqqqueuqueuuuueuueeuueueeququeeeqeeqeeqqeuqeuequququuuuuueuuueeeuueeeqeuqquueuueeuquuqqqeqeuqqeqqquuueuuuuueeuuqeeeeeeeueuuuququeqqqqeeuqeuuquuueueeuuuqeqeeuqqqquuuq...
output:
((((((()()))((((()(((((()(()((((()))((((()((((((()(()))((((())))((((((()()))(((((((((())()))())(()()(((((((((((((((()))(()((((())(()))((()))))((((((((((())))(()((((((((())))())(((((((((((((())((()(((()(((((((((((((())(()(((((((()(((((((((((((()()(((((((((((()((((((((((((((()((((((()())(((()((())(()(...
result:
ok single line: '((((((()()))((((()(((((()(()((...))))((())))())))((())))))()))))'
Subtask #3:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #8:
score: 63
Accepted
time: 39ms
memory: 8400kb
input:
jggeedfjvfppgdgqqufesgeljdjjoqqsgprqdddgueugpodpfldvgdgdpeuljfqrdrlgljugdujjdjrjevlqlqufoosjvsqvqgvruqrgsfsquqoovvvvfpofjdpvuesrqdfegguggrlvslsqjpddorjlodqflspgopeuppeoleeojlvjpddopjsouregflrfgpgqvlquqpplgrudllvdfsrplfljupveleggedljopqjjolslfpeeluvsufofpdlodgdvfvsujlgjpvggduorfforllorgsgrppvegglgver...
output:
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((())((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((()(((((((((...
result:
ok single line: '((((((((((((((((((((((((((((((...)))))))))))))))))))))))))))))))'
Test #9:
score: 0
Accepted
time: 617ms
memory: 19180kb
input:
zpujdttdnwtkfdfyddtbocyaeniizwubzgeybkccezxjldgtskmjfdywqlrihhckmbmvewoludvvmamdgkeholteaqujgssidpivwljbsnqgxltiviiwsvtekxiftlfkkudkwmbqczskkjsnilevhvdmuelnufvftyphloppctvwksjffecxblezsryszkxrjthxowwrittvjinyfkklllkydvzciiuaayomqjulladasktsyrvffdeennbwelfnhqoisiommrolzfvzkddskonisxlasgckqioouyqtsqfq...
output:
((((((((((((((((()((((((((((((((((((((()((((((((((((((((((((((((((((((((((()(((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((()(((((((((((((((((((((((((()(((((((((((((((((((((((((((((((((()(((((((((((((((((()(()((((((((((((((((((()(((()(((((((((((((()((((((((()(((((((((((((((((((((((((...
result:
ok single line: '((((((((((((((((()((((((((((((...)))))))))))))))))))))))))))))))'
Test #10:
score: 0
Accepted
time: 755ms
memory: 20012kb
input:
azekdamqaoetekbsselhazotlwwjnpxxceapyxsvgxutdtnnzzvovngkkrwvjrlddncosheotmepxghaeiakddfjzugxqunauvcbyipxtzkrjsdrjbcaozefshjwyrbdviigqvrpkkeamsvnkoyafpululfzaakbwgjkhfpnwihzeuwmydiazwjujussexlzbriochtfyvwbgpduxnkwvpycobczuuzmytnlllrvtyhzzwawtzkamqucyauxrlgthhayaidysemasybwnkjjiqoscacwsqprwjdfshttqriq...
output:
((((((((((((((((((((((((((((((()((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((((()((((((((((((((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((...
result:
ok single line: '((((((((((((((((((((((((((((((...))))))))()))))))))))))())))))))'
Test #11:
score: 0
Accepted
time: 1252ms
memory: 22928kb
input:
mldshhxgdtnevvjvvvmdxxppbbrxxtpwboorjjrgpmmmnvthhjjtvbrpxpsxxsjjxtjjtpbevhhvvduprhjshccwoggsllsdcbbuubbutlojstebhrpnwsoxnopprssbuljwmxvgpprwlxnossuggmovhsggcbddprrhsthwnsleevshtnlodsjelhntswuultovcbbclndjjhnvvwewvodnmpslwnseupvccvshuusxvunnmoeeggoobbttsojjnjpvxdewnnndnlmeebprppsrppjcessehrrjnuutgpco...
output:
((((((((((((()((()((()()()(((((((()(()(((((((((()()))(((((((((()((())((((()()((((((((()((()(())((((()))(((((((((((((((((((()((((((((((((()(((((((((()(((((()((()(((((((((((()(((((((((((((((((()(((((())(((()((((((((((((((((((((((())((()((((()((()()()()((((()(((((((((()((((((((((((((((((())(((((()(((((...
result:
ok single line: '((((((((((((()((()((()()()((((...))))))))))))))()))))))()))))())'
Test #12:
score: -63
Time Limit Exceeded
input:
baabbabaaaaababababaabaababbbaababaabaaabbabbbaaababababbababaaaabaaaabbaaaababbabaabababababababbaabbaaabbbbbbaaabbbabbbabbaaaabbbbabaabaaabbbbabaabbbaabbbbaaaabababbbaabbbaabaabbbababbbabbbabaabbbabbaaaababaabaabbabbbbaababbabaaabaaaabbbaabaabaaabbaaabbaaaabaabbaaaabaabbbbabababaababbbaabbbbababbb...