Untitled
unknown
plain_text
a year ago
1.3 kB
17
Indexable
#include <bits/stdc++.h> using namespace std; #define int long long bool f(int len,int n,int*left_,int*right_){ if(len == 0)return true; if(2*len > n)return false; for(int i=0;i + (2*len) - 1 < n;i++){ int left_c = left_[i + len - 1] - (i > 0 ? left_[i-1] : 0); int right_c = right_[i + 2*len - 1] - right_[i + len - 1]; if((left_c == right_c) && (left_c == len))return true; } return false; } void solve(){ int n;cin>>n; string st; cin>>st; int left_[n]; int right_[n]; memset(left_,0,sizeof(left_)); memset(right_,0,sizeof(right_)); if(st[0] == '<')left_[0] = 1; for(int i=1;i<n;i++){ left_[i] = left_[i-1]; if((st[i] == '<') || (st[i] == '?'))left_[i]++; } if(st[0] == '>')right_[0] = 1; for(int i=1;i<n;i++){ right_[i] = right_[i-1]; if(st[i] == '>' || st[i] == '?')right_[i]++; } int low = -1; int high = (n + 1)/2; int mid; while(low + 1 < high){ mid = (high + low)/2; if(f(mid,n,left_,right_) == true){ low = mid; }else high = mid; } cout<<2*low<<endl; } int32_t main(){ int t;cin>>t; while(t--)solve(); }
Editor is loading...
Leave a Comment