oj.uz

Submission #488735

# Submission time Handle Problem Language Result Execution time Memory
488735 2021-11-20T09:30:50 Z boris_mihov Parking Problem (innopolis2021_final_A) C++14
54 / 100
 16 ms 1744 KB 
#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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1624 KB Output is correct
2 Correct 5 ms 1232 KB Output is correct
3 Correct 14 ms 1488 KB Output is correct
4 Correct 7 ms 1648 KB Output is correct
5 Correct 6 ms 1264 KB Output is correct
6 Correct 7 ms 1684 KB Output is correct
7 Correct 6 ms 1232 KB Output is correct
8 Correct 15 ms 1440 KB Output is correct
9 Correct 4 ms 1488 KB Output is correct
10 Correct 5 ms 1232 KB Output is correct
11 Correct 15 ms 1520 KB Output is correct
12 Correct 5 ms 1744 KB Output is correct
13 Correct 5 ms 1224 KB Output is correct
14 Correct 15 ms 1532 KB Output is correct
15 Correct 13 ms 1068 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1656 KB Output is correct
2 Correct 5 ms 1232 KB Output is correct
3 Correct 15 ms 1492 KB Output is correct
4 Incorrect 6 ms 1744 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1616 KB Output is correct
2 Correct 6 ms 1360 KB Output is correct
3 Correct 6 ms 1232 KB Output is correct
4 Correct 8 ms 1300 KB Output is correct
5 Correct 10 ms 1360 KB Output is correct
6 Correct 11 ms 1360 KB Output is correct
7 Correct 14 ms 1360 KB Output is correct
8 Correct 16 ms 1416 KB Output is correct
9 Correct 14 ms 1048 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1624 KB Output is correct
2 Correct 5 ms 1232 KB Output is correct
3 Correct 14 ms 1488 KB Output is correct
4 Correct 7 ms 1648 KB Output is correct
5 Correct 6 ms 1264 KB Output is correct
6 Correct 7 ms 1684 KB Output is correct
7 Correct 6 ms 1232 KB Output is correct
8 Correct 15 ms 1440 KB Output is correct
9 Correct 4 ms 1488 KB Output is correct
10 Correct 5 ms 1232 KB Output is correct
11 Correct 15 ms 1520 KB Output is correct
12 Correct 5 ms 1744 KB Output is correct
13 Correct 5 ms 1224 KB Output is correct
14 Correct 15 ms 1532 KB Output is correct
15 Correct 13 ms 1068 KB Output is correct
16 Correct 6 ms 1656 KB Output is correct
17 Correct 5 ms 1232 KB Output is correct
18 Correct 15 ms 1492 KB Output is correct
19 Incorrect 6 ms 1744 KB Output isn't correct
20 Halted 0 ms 0 KB -