제출 #488735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
488735		boris_mihov	Parking Problem (innopolis2021_final_A)	C++14	54 / 100	16 ms	1744 KiB

Main

#include <iostream>
#include <vector>
using namespace std;
const int maxn = 1e5+10;

string s, q, output;
vector < int > spaces;
int n, m, t;

bool greedy(int when) {

    int cntc = 0, cntm = 0;
    for (int i = 0 ; i <= when-1 ; ++i) {
    
        cntc += (q[i] == 'C');
        cntm += (q[i] == 'M');
    
    }

    for (int i : spaces) {

        if (cntc == 0) {

            cntm -= (i/2 + i%2);
            if (cntm < 0) return 1;
            continue;

        }

        if (cntm == 0) {

            cntc -= (i/3 + (i%3 > 0));
            if (cntc < 0) return 1;
            continue;

        }

        if (i % 3 == 0) {

            int remove = min(cntc, i/3);
            cntc -= remove;
            cntm -= (i - remove*3)/2 + (i - remove*3)%2;
            if (cntm < 0) return 1;
            continue;

        }

        if (i % 3 == 1) {

            if (i == 1) {

                --cntm;
                continue;

            }

            int remove = min(cntc, (i-4)/3);
            if (cntm < 2) ++remove;
            cntc -= remove;
            cntm -= (i - remove*3)/2 + (i - remove*3)%2;
            if (cntc < 0 || cntm < 0) return 1;
            continue;

        }

        if (i % 3 == 2) {

            int remove = min(cntc, i/3);
            cntc -= remove;
            cntm -= (i - remove*3)/2 + (i - remove*3)%2;
            if (cntm < 0) return 1;
            continue;

        }

    }

    return 0;

}

void reset() {

    spaces.clear();
    output.clear();

}

void solve() {

    int curr = 0;
    for (char c : s) {

        if (c == 'X') {

            if (curr >= 2) spaces.push_back(curr-1);
            curr = 0;

        } else {

            ++curr;

        }

    }

    if (curr >= 2) spaces.push_back(curr-1);

    // cout << "spaces: \n";
    // for (int i : spaces)
    //     cout << i << ' ';
    // cout << '\n';

    int l = -1, r = m+1, mid;
    while (l < r - 1) {

        mid = (l+r)/2;
        if (greedy(mid)) l = mid;
        else r = mid;

    }

    output.resize(m+1);
    for (int i = 0 ; i <= m ; ++i) {

        if (i <= l) output[i] = 'Y';
        else output[i] = 'N';

    }

    cout << output << '\n';

}

void fast_io() {

    ios_base :: sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cerr.tie(nullptr);

}

void read() {

    cin >> s;
    cin >> q;

    n = s.size();
    m = q.size();

}

int main () {

    fast_io();
    cin >> t;

    while (t--) {

        reset();
        read();
        solve();

    }

    return 0;

}

/*
1
.X..X.
MMM
*/

• Subtask 1: 31 / 31
• Subtask 2: 0 / 22
• Subtask 3: 23 / 23
• Subtask 4: 0 / 24