Submission #445633

#TimeUsernameProblemLanguageResultExecution timeMemory
445633alirezasamimi100Match (CEOI16_match)C++17
0 / 100
0 ms204 KiB
#include <bits/stdc++.h> /*#pragma GCC optimize("Ofast,unroll-loops") #pragma comment(linker, "/stack:200000000") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")*/ /*#pragma GCC optimize("O2") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,sse,sse2,fma")*/ using namespace std; using ll = long long int; using ld = long double; using pll=pair<ll,ll>; using pii=pair<int,int>; #define F first #define S second #define pb push_back //#define mp make_pair #define lc v<<1 #define rc v<<1|1 #define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); const int N=2e5+10,LN=19,M=14348907,SQ=350,BS=737,inf=1e9+10; const ll INF=1e18; const ld ep=1e-7; const int MH=1000696969,MD=1000000007,MOD=998244353; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update> ll pow(ll x, ll y, ll mod){ ll ans=1; while (y != 0) { if (y & 1) ans = ans * x % mod; y >>= 1; x = x * x % mod; } return ans; } string s; ll n; char ans[N]; vector<ll> st,id[26]; bool ck(ll l, ll r){ st={}; for(ll i=l; i<=r; i++){ if(st.empty() || s[st.back()]!=s[i]) st.pb(i); else st.pop_back(); } return st.empty(); } void sol(ll l, ll r){ if(l>r) return; ll x=s[l]-'a'; for(ll i=id[x].size()-1; id[x][i]>l; i--){ if(ck(l+1,id[x][i]-1) && ck(id[x][i]+1,r)){ ans[l]='('; ans[id[x][i]]=')'; sol(l+1,id[x][i]-1); sol(id[x][i]+1,r); return; } } } int main(){ fast_io; cin >> s; n=s.size(); for(ll i=0; i<n; i++){ id[s[i]-'a'].pb(i); if(st.empty() || s[st.back()]!=s[i]) st.pb(i); else{ st.pop_back(); } } if(!st.empty()){ cout << -1 << '\n'; return 0; } sol(0,n-1); for(ll i=0; i<n; i++) cout << ans[i]; cout << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...