QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#460681 | #5534. Match | fryan# | 10 | 1ms | 3528kb | C++20 | 1.4kb | 2024-07-02 01:16:16 | 2024-07-02 01:16:16 |
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;
int n, s[mxn], cnt[26];
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
string ss; cin >> ss;
n = sz(ss);
for (int i=0; i<n; i++) {
s[i] = ss[i]-'a';
cnt[s[i]]++;
}
for (int i=0; i<n; i++) {
if (cnt[i]&1) {
cout<<-1; return 0;
}
}
vector<int> stk, brk;
for (int i=0; i<n; i++) {
int f = s[i];
vector<int> stk1 = stk;
//case 1 - insert
stk1.push_back(f);
for (int j=i+1; j<n; j++) {
int cf = s[j];
if (stk1[sz(stk1)-1]==cf) {
stk1.pop_back();
} else {
stk1.push_back(cf);
}
}
if (!sz(stk1)) {
stk.push_back(f);
brk.push_back(0);
continue;
}
//case 2 - put back
if (!sz(stk) || stk[sz(stk)-1]!=f) {
cout<<-1; return 0;
} else {
stk.pop_back();
brk.push_back(1);
}
}
for (int i:brk) {
cout << (i ? ')' : '(');
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 3480kb
input:
abbaaa
output:
(()())
result:
ok single line: '(()())'
Test #2:
score: 10
Accepted
time: 1ms
memory: 3404kb
input:
cbbbbccbbccbbbbbbc
output:
(((((((()))())))))
result:
ok single line: '(((((((()))())))))'
Test #3:
score: 10
Accepted
time: 1ms
memory: 3520kb
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: 1ms
memory: 3528kb
input:
fsooskkkksokkkkossskkiffoofooikkiiiiiooikkkksookkiissiooookskffsskiiksskiikfiifkifofssooffffkfiiiifkfsiisfsofossiffissikskiikkkiikokikkffkiiksffkkiossifkiookioffoikkkoiiiooioiffkkkssfoooiiiioioskksisikkkoifiooikkkkfiffississkskiofffiffiiiosksskfffofisksksskiisikkskkkksoosiffoofoiooioooifiifssfffffoi...
output:
-1
result:
wrong answer 1st lines differ - expected: '((((((())))(()))(((()(((()((((...))(())(()))(())())))))))((())))', found: '-1'
Subtask #3:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%