# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
56823 |
2018-07-12T16:46:55 Z |
mraron |
Match (CEOI16_match) |
C++14 |
|
4 ms |
620 KB |
/*
ID: noszaly1
TASK: {TASK}
LANG: C++11
*/
//Noszály Áron 10o Debreceni Fazekas Mihály Gimnázium
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const double PI=acos(-1);
template<typename T> T getint() {
T val=0;
char c;
bool neg=false;
while((c=gc()) && !(c>='0' && c<='9')) {
neg|=c=='-';
}
do {
val=(val*10)+c-'0';
} while((c=gc()) && (c>='0' && c<='9'));
return val*(neg?-1:1);
}
ll mod=1e9+7;
ll p=31;
string t;
ll st[100001], en[100001];
map<int, vector<int>> lst;
string ans;
void solve(int L, int R) {
if(L>R) return ;
//cerr<<L<<" "<<lst[en[L]].back()<<" "<<R<<"\n";
assert(lst[en[L]].back()<=R);
int par=lst[en[L]].back();
ans[L]='(';
ans[par]=')';
lst[en[L]].pop_back();
solve(par+1, R);
solve(L+1, par-1);
}
int main() {
IO;
cin>>t;
stack<pair<char,ll>> s;
int ind=0;
for(auto i:t) {
if(s.empty()) {
st[ind]=-1;
}else {
st[ind]=s.top().yy;
}
if(!s.empty() && s.top().xx==i) {
s.pop();
}else {
if(s.empty()) {
s.push({i, i});
}else {
s.push({i, (i+p*s.top().yy)%mod});
}
}
if(s.empty()) {
en[ind]=-1;
}else {
en[ind]=s.top().yy;
}
ind++;
}
if(!s.empty()) {
cerr<<"-1\n";
return 0;
}
for(int i=0;i<sz(t);++i) {
lst[st[i]].pb(i);
}
ans=string(sz(t), '*');
solve(0, sz(t)-1);
cout<<ans<<"\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Runtime error |
4 ms |
620 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Runtime error |
4 ms |
620 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Runtime error |
4 ms |
620 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |