Suiiinaldo's blog

By Suiiinaldo, history, 13 months ago, In English

I am getting WA at Pretest 2 and the token which is differentiated is 252. I don't know if there is any corner cases, because it is passed at edge case like substring length = 7.Please help. The problem link is attached below 1605C - Dominant Character

My submission is stated below: 231633540


#include<bits/stdc++.h> #define upper(s) transform(s.begin(),s.end(),s.begin(),::toupper) #define lower(s) transform(s.begin(),s.end(),s.begin(),::tolower) #define all(s) s.begin(),s.end() #define rep(n) for(int i=0;i<n;i++) #define repn(i,a,b) for(int i =a;i<b;i++) #define showvec(v) for(int i=0;i<v.size();i++) cout<<v[i]<<" ";cout<<endl #define showmap(m) for(auto i=m.begin();i!=m.end();++i) cout<<i->first<<" "<<i->second<<endl; #define showset(s) for(auto i=s.begin();i!=s.end();++i) cout<<*i<<" ";cout<<endl; #define ll long long #define endl '\n' #define int long long #define pii pair<int,int> using namespace std; //x<<y is x*(2^y) //x>>y is x/(2^y) void solve() { int n; cin>>n; string s; cin>>s; int mini = INT_MAX; vector<int> aIndex; vector<int> bOccur(n); vector<int> cOccur(n); bOccur[0] = s[0] == 'b' ? 1 : 0; cOccur[0] = s[0] == 'c' ? 1 : 0; for(int i = 0;i<n;i++) { if(s[i] == 'a') aIndex.push_back(i); } for(int i = 1;i<n;i++) { bOccur[i] = (s[i] == 'b') ? bOccur[i-1]+1 : bOccur[i-1]; cOccur[i] = (s[i] == 'c') ? cOccur[i-1]+1 : cOccur[i-1]; } if(aIndex.size() <= 1) { cout<<"-1\n"; return; } int low = 0,high = 1; n = aIndex.size(); while(low < high and high < n) { if(bOccur[aIndex[high]] - bOccur[aIndex[low]] >= high - low + 1 or cOccur[aIndex[high]] - cOccur[aIndex[low]] >= high - low + 1) { high++; } else { mini = min(mini,aIndex[high] - aIndex[low] + 1); low = high; high += 1; } } if(mini == INT_MAX) cout<<"-1\n"; else cout<<mini<<endl; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); int t; cin>>t; while(t-->0) { solve(); } return 0; }
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it
Spoiler