?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
100067682 |
Practice: obliviousz |
1248D1 - 32 | C++17 (GCC 7-32) | Accepted | 732 ms | 8 KB | 2020-11-30 23:33:34 | 2020-11-30 23:33:34 |
#pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; #define gcd(a,b) __gcd(a,b) #define pb(x) push_back(x) #define L length() #define mkp(x,y) make_pair(x,y) #define int long long #define bs binary_search #define mod 1e9+7 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define all(v) v.begin(),v.end() #define allr(v) v.rbegin(),v.rend() #define mem0(a) memset(a,0,sizeof(a)) #define mem1(a) memset(a,-1,sizeof(a)) #define F first #define S second #define pii pair<int,int> #define vi vector<int> #define vs size() //#define endl '\n' #define atoi stoi #define elasped_time 1.0 * clock() / CLOCKS_PER_SEC #define si set <int> #define vpii vector < pair <int,int> > #define memf(a) memset(a,false,sizeof(a)) #define memt(a) memset(a,true,sizeof(a)) #define xxx 998244353 #define pi 3.141592653589 #define ninf INT_MIN #define inf 1e9+7 #define sz(v) ((int)(v).size()) #define rep(i,a,b) for(int i=a;i<=b;i++) #define FILL(a,x) memset(a,x,sizeof(a)) int max(int a,int b){if(a>b){return a;}else{return b;}} int min(int a,int b){if(a<b){return a;}else{return b;}} int power(int b,int e) { if(e==0) return 1; if(e%2) return ((b*power((b)*(b),(e-1)/2))); else return power((b)*(b),e/2); } int modpower(int b,int e,int q) { int MOD=q; if(e==0) return 1; if(e%2) return ((b%MOD)*modpower((b%MOD)*(b%MOD),(e-1)/2,q))%MOD; else return modpower((b%MOD)*(b%MOD),e/2,q)%MOD; } void dpv(vi v) { for(int i=0;i<v.vs;i++) { cout<<v[i]<<" "; } cout<<endl; } void dpv(vpii v) { for(int i=0;i<v.vs;i++) { cout<<v[i].F<<" "<<v[i].S<<endl; } } void dpv(set <int> v) { for(auto i:v) { cout<<i<<" "; } cout<<endl; } //////////////////////**TREE MOVES STARTS**////////////////////////////// ///// **TREE MOVES ENDS**//////////////////////////// ////*SOLUTION TO THE QUESTION STARTS HERE*////// const int N=1e5+5; const int MOD=1e9+7; void oblivious() { int n; cin>>n; string s; cin>>s; int bal=0; for(int i=0;i<n;i++) { if(s[i]=='(') { bal++; } else { bal--; } } if(bal) { cout<<0<<endl; cout<<1<<" "<<1<<endl; return; } int mx=-inf; int l=1,r=1; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { swap(s[i],s[j]); vi v(n,0); if(s[0]=='(') { v[0]=1; } else { v[0]=-1; } int mi=v[0]; for(int k=1;k<n;k++) { v[k]=v[k-1]; if(s[k]=='(') { v[k]++; } else { v[k]--; } mi=min(mi,v[k]); } int cnt=count(all(v),mi); if(mx<cnt) { l=i+1; r=j+1; mx=max(mx,cnt); } swap(s[i],s[j]); } } cout<<mx<<endl; cout<<l<<" "<<r<<endl; } signed main() { IOS; //FILL(dp,0); //Try this case /*#ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif*/ int t=1; //cin>>t; //int z=t; while(t--) { //cout<<"Case #"<<(z-t)<<": "; oblivious(); } return 0; } //Editorial /* ABAAAABBBAABAAB //*/
?
?
?
?