QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #591592 | #5534. Match | xiay | 10 | 922ms | 5768kb | C++14 | 1.3kb | 2024-09-26 16:40:37 | 2024-09-26 16:40:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
string s;
int a[N];
int sum[30][N];
int n;
stack <char> st;
int lst[N], nxt[N];
bool check(int l, int r) {
for (int i = 0; i < 26; i++) {
if ((sum[i][r] - sum[i][l - 1]) & 1) {
return 0;
}
}
int sum = 0;
for (int i = l; i <= r; i++) {
if (!a[i]) {
sum++;
}
else {
if (!sum) {
return 0;
}
sum--;
}
}
return 1;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
cin >> s;
n = s.size();
s = " " + s;
for (int i = 1; i <= n; i++) {
nxt[lst[s[i] - 'a']] = i;
lst[s[i] - 'a'] = i;
if (st.empty() || st.top() != s[i]) {
st.push(s[i]);
}
else {
st.pop();
a[i] = 1;
}
for (int j = 0; j < 26; j++) {
sum[j][i] = sum[j][i - 1];
}
sum[s[i] - 'a'][i]++;
}
if (!st.empty()) {
puts("-1");
return 0;
}
while (1. * clock() / CLOCKS_PER_SEC < 0.97) {
for (int j = 1; j <= n; j++) {
if (nxt[j] && a[nxt[j]] < a[j]) {
if (check(j + 1, nxt[j] - 1)) {
swap(a[nxt[j]], a[j]);
}
}
}
}
for (int i = 1; i <= n; i++) {
if (a[i]) {
putchar(')');
}
else {
putchar('(');
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 307ms
memory: 3972kb
input:
abbaaa
output:
(()())
result:
ok single line: '(()())'
Test #2:
score: 10
Accepted
time: 452ms
memory: 5768kb
input:
cbbbbccbbccbbbbbbc
output:
(((((((()))())))))
result:
ok single line: '(((((((()))())))))'
Test #3:
score: 10
Accepted
time: 1ms
memory: 3632kb
input:
ddbcbdacccbddaba
output:
-1
result:
ok single line: '-1'
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #4:
score: 0
Wrong Answer
time: 922ms
memory: 3860kb
input:
fsooskkkksokkkkossskkiffoofooikkiiiiiooikkkksookkiissiooookskffsskiiksskiikfiifkifofssooffffkfiiiifkfsiisfsofossiffissikskiikkkiikokikkffkiiksffkkiossifkiookioffoikkkoiiiooioiffkkkssfoooiiiioioskksisikkkoifiooikkkkfiffississkskiofffiffiiiosksskfffofisksksskiisikkskkkksoosiffoofoiooioooifiifssfffffoi...
output:
((((((())))(()))())()(((()((((()(()))))((())(()()((())(())(((()(((())))(()))()))((((()()(())(((())))((()))(((((((())))((((()(()())(((((())())(()()((()((((()(((()))())((()())))()())())(()(()))))(()))))()))(((())(()))(())())())))))())(()())))(())()))))))((())()))()((()))()))()())((())()))(()(()(()))((...
result:
wrong answer 1st lines differ - expected: '((((((())))(()))(((()(((()((((...))(())(()))(())())))))))((())))', found: '((((((())))(()))())()(((()((((...))(())(()))(())()))()(()(()))))'
Subtask #3:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%