제출 #527765

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

Main

#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/2 != 0 ; ++i) {

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

    }

    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;

}

컴파일 시 표준 에러 (stderr) 메시지

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

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