fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int N = 2e5+10;
  5. vector<int> A;
  6.  
  7. void solve() {
  8.    int n; cin >> n;
  9.    string s; cin >> s;
  10.    int oz = 0, zo = 0;
  11.    int inv = 0;
  12.    int one=0;
  13.    for(int i = 0; i < n-1; i++) {
  14. 	if(s[i] != s[i+1]) inv++;
  15. 	if(s[i] == '0' && s[i+1] == '1') zo++;
  16. 	else if(s[i] == '1' && s[i+1] == '0') oz++;
  17. 	if(s[i] == '1') one++;
  18.    }
  19.    if(s[n-1] == '1') one++;
  20.    int f1 = 0, f0 = 0;
  21.    if(s[0] == '1') f1 = 1;
  22.    if(s[n-1] == '1') f0 = 1;
  23.    if(oz >= 2 || zo >= 2) {
  24.    	cout << n + inv + f1 - 2 << endl;
  25.    	return;
  26.    }
  27.    if(one == n) {
  28.    	cout << n+1 << endl;
  29.    	return;
  30.    }
  31.    if(inv == 0) {
  32.    	cout << n <<endl;
  33.    	return;
  34.    }
  35.    if(inv == 1) {
  36.    	cout << n+1 <<endl;
  37.    	return;
  38.    }
  39.    if(f1==0) {
  40.    	cout << n + inv - 1 << endl;
  41.    	return;
  42.    }
  43.    cout << n + inv  << endl;
  44.  
  45. }
  46.  
  47. signed main() {
  48.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  49.     //freopen("Error.txt", "w", stderr);
  50.     //freopen("input.txt", "r", stdin);
  51.     //freopen("output.txt", "w", stdout);
  52.     int t = 1;  cin >> t;
  53.     while(t--) {solve();}
  54. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
6
3
000
3
111
3
011
3
100
5
10101
19
1101010010011011100
stdout
copy 
3
4
4
4
8
29
https://ideone.com/X0JQlZ
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!