oj.uz

Submission #527761

# Submission time Handle Problem Language Result Execution time Memory
527761 2022-02-18T08:48:02 Z boris_mihov Parking Problem (innopolis2021_final_A) C++14
23 / 100
 17 ms 1752 KB 
#include <iostream>
const int maxn = 1e5+10;

std::string s, vehicles, ans;
int a[maxn], b[maxn], n, m;
int ccnt, mcnt;

bool check(int to) {

    ccnt = 0;
    mcnt = 0;

    for (int i = 0 ; i < to ; ++i) {

        ccnt += (vehicles[i] == 'C');
        mcnt += (vehicles[i] == 'M');

    }

    for (int i = 1 ; i <= m ; ++i) b[i] = a[i];
    for (int i = 1 ; i <= m && ccnt != 0 ; ++i) {

        if (b[i] % 2 == 1 && b[i] != 1) {

            b[i] -= 3;
            --ccnt;

        }

    }

    for (int i = 1 ; i <= m && ccnt != 0 ; ++i) {

        int cost = b[i]/6;
        b[i] -= 6*std::min(cost, ccnt);
        ccnt -= std::min(cost, ccnt);

    }

    mcnt += ccnt;
    int sum = 0;

    for (int i = 1 ; i <= m ; ++i) 
        sum += b[i]/2 + b[i]%2;

    // std::cout << "check: " << to << ' ' << sum << ' ' << mcnt << '\n';
    return mcnt <= sum-1;

}

void solve() {

    n = vehicles.size();

    m = 0;
    int curr = 0;
    for (int i = 0 ; i < s.size() ; ++i) {

        if (s[i] == '.') ++curr;
        else {

            if (curr >= 2) a[++m] = curr-1;
            curr = 0;

        }

    }

    if (curr >= 2) a[++m] = curr-1;

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

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

    }

    ans.clear();
    ans.resize(n+1);
    for (int i = 0 ; i <= l ; ++i) ans[i] = 'Y';
    for (int i = l+1 ; i <= n ; ++i) ans[i] = 'N';

    std::cout << ans << '\n';

}

void read() {

    std::cin >> s;
    std::cin >> vehicles;

}

void fast_io() {

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

}

int t;
int main () {

    fast_io();
    
    std::cin >> t;
    while (t--) {
    
        read();
        solve();
    
    }

    return 0;

}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:57:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 0 ; i < s.size() ; ++i) {
      |                      ~~^~~~~~~~~~

Subtask #1
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1488 KB Output is correct
2 Correct 6 ms 1224 KB Output is correct
3 Correct 17 ms 1440 KB Output is correct
4 Incorrect 8 ms 1640 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1680 KB Output is correct
2 Correct 6 ms 1232 KB Output is correct
3 Correct 17 ms 1456 KB Output is correct
4 Incorrect 7 ms 1752 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 8 ms 1700 KB Output is correct
2 Correct 7 ms 1312 KB Output is correct
3 Correct 7 ms 1380 KB Output is correct
4 Correct 7 ms 1340 KB Output is correct
5 Correct 10 ms 1352 KB Output is correct
6 Correct 11 ms 1340 KB Output is correct
7 Correct 14 ms 1400 KB Output is correct
8 Correct 17 ms 1512 KB Output is correct
9 Correct 15 ms 988 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1488 KB Output is correct
2 Correct 6 ms 1224 KB Output is correct
3 Correct 17 ms 1440 KB Output is correct
4 Incorrect 8 ms 1640 KB Output isn't correct
5 Halted 0 ms 0 KB -