/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Wrong Answer 6ms 784.0 KiB
#3 Wrong Answer 4ms 540.0 KiB

Code

// PIPRA ||  HABIB
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define int        long long int
#define pb         push_back
#define all(x)     x.begin(),x.end()
#define allr(x)    x.rbegin(),x.rend()
#define ii         pair<int,int>
#define endl       "\n"

template<typename T>
ostream& operator<<(ostream &os, const vector<T> &v) {
os << '{'; for (const auto &x : v) os << " " << x; return os << '}';
}
using orderedTree = tree<int, null_type, less<int>, 
rb_tree_tag, tree_order_statistics_node_update>;

void pipra(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int one = 0, cnt = 1;
    bool ok = 0;

    vector<int> pre(n), suf(n);
    pre[0] = suf[n - 1] = 1;
    if(s[0] == '1' or s[n - 1] == '1')
    	one = 1;

    for(int i = 1 ; i < n ; i++) {
    	if(s[i] != s[i - 1]) {
    		pre[i] = 1;
    	}
    	else {
    		pre[i] = pre[i - 1] + 1;
    	}
    	if(s[i] == '1')
    		one = max(one, pre[i]);
    }
    for(int i = n - 2 ; i >= 0 ; i--) {
    	if(s[i] != s[i + 1]) {
    		suf[i] = 1;
    	}
    	else {
    		suf[i] = suf[i + 1] + 1;
    	}
    	if(s[i] == '1')
    		one = max(one, suf[i]);
    }

    for(int i = 1 ; i < n - 1 ; i++) {
    	if(s[i] == '0' and s[i - 1] == '1' and s[i + 1] == '1') {
    		if((pre[i - 1] + suf[i + 1] + 1) > one) {
    			ok = 1;
    			one = max(one, pre[i - 1] + suf[i + 1] + 1);
    		}
    	}
    }
    if(one != n and !ok)
    	one++;

    cout << ((one + 1) >> 1) << endl;
}

int32_t main(){
    // HABIB
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);

    int t;    cin>>t;
    while(t--) {
        pipra();
    }
    return 0 ;
}

Information

Submit By
Type
Submission
Problem
P1113 Fliping Game
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-07 09:01:00
Judged At
2024-11-07 09:01:00
Judged By
Score
5
Total Time
6ms
Peak Memory
784.0 KiB