/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 332.0 KiB
#2 Wrong Answer 11ms 580.0 KiB
#3 Wrong Answer 5ms 328.0 KiB

Code

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int calculateMaxConsecutiveOnes(const string& S) {
    int maxOnes = 0;
    int currentOnes = 0;
    for (char c : S) {
        if (c == '1') {
            currentOnes++;
            maxOnes = max(maxOnes, currentOnes);
        } else {
            currentOnes = 0;
        }
    }
    return maxOnes;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;
        string S;
        cin >> S;

        // Flip the characters optimally by simulating the moves of Roy and Emon
        vector<int> one_segments, zero_segments;
        int current_segment_length = 0;
        char last_char = '2';  // initialize to an invalid character different from '0' or '1'

        // First, identify all segments of consecutive '0's and '1's
        for (int i = 0; i < N; i++) {
            if (S[i] == last_char) {
                current_segment_length++;
            } else {
                if (last_char == '0') zero_segments.push_back(current_segment_length);
                if (last_char == '1') one_segments.push_back(current_segment_length);
                current_segment_length = 1;
                last_char = S[i];
            }
        }

        // Add the last segment to the respective vector
        if (last_char == '0') zero_segments.push_back(current_segment_length);
        if (last_char == '1') one_segments.push_back(current_segment_length);

        // Sort zero_segments in descending order (to allow Roy to maximize when flipping 0s)
        sort(zero_segments.rbegin(), zero_segments.rend());

        // Roy starts the game and can choose the largest segment of zeroes to flip to '1'
        int result = 0;
        if (!zero_segments.empty()) result = zero_segments[0];

        // Calculate the maximum consecutive ones considering initial segments and flipped segments
        result = max(result, calculateMaxConsecutiveOnes(S));

        cout << result << "\n";
    }

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1113 Fliping Game
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-06 13:59:37
Judged At
2024-11-11 02:24:56
Judged By
Score
5
Total Time
11ms
Peak Memory
580.0 KiB