Submission #58152

#	Time	Username	Problem	Language	Result	Execution time	Memory
58152		choikiwon	Toilets (JOI16_toilets)	C++17	100 / 100	634 ms	12644 KiB

toilets

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MN = 100010;

ll N, msum;
int M;
string S[MN];
ll K[MN];

vector<string> T;
vector<ll> X;

void rem(char c, char o, ll x) {
    vector<string> tt = T;
    vector<ll> xx = X;
    T.clear();
    X.clear();

    for(int i = (int)tt.size() - 1; i >= 0; i--) {
        int cnt = 0;
        for(int j = 0; j < tt[i].size(); j++) if(tt[i][j] == c) cnt++;
        if(x) {
            if(x >= xx[i] * cnt) {
                if((int)tt[i].size() - cnt) {
                    T.push_back("");
                    T.back().push_back(o);
                    X.push_back(xx[i] * ((int)tt[i].size() - cnt));
                }
                x -= xx[i] * cnt;
            }
            else {
                ll q = x / cnt;
                if(q && (int)tt[i].size() - cnt) {
                    T.push_back("");
                    T.back().push_back(o);
                    X.push_back(q * ((int)tt[i].size() - cnt));
                }
                x -= q * cnt;
                xx[i] -= q;

                string tmp;
                cnt = 0;
                for(int j = (int)tt[i].size() - 1; j >= 0; j--) {
                    if(tt[i][j] == c) {
                        if(cnt >= x) tmp.push_back(c);
                        cnt++;
                    }
                    else tmp.push_back(o);
                }
                reverse(tmp.begin(), tmp.end());
                T.push_back(tmp);
                X.push_back(1);

                if(xx[i] > 1) {
                    T.push_back(tt[i]);
                    X.push_back(xx[i] - 1);
                }
                x = 0;
            }
        }
        else {
            T.push_back(tt[i]);
            X.push_back(xx[i]);
        }
    }
    reverse(T.begin(), T.end());
    reverse(X.begin(), X.end());
}

void rev() {
    for(int i = 0; i < T.size(); i++) {
        reverse(T[i].begin(), T[i].end());
    }
    reverse(T.begin(), T.end());
    reverse(X.begin(), X.end());
}

bool check(ll x) {
    T.clear();
    X.clear();
    if(x) {
        T.push_back("M");
        X.push_back(x);
    }
    for(int i = 0; i < M; i++) {
        T.push_back(S[i]);
        X.push_back(K[i]);
    }

    rem('M', 'F', x);
    rev();
    rem('F', 'M', 2 * N - 2 * msum);
    rev();

    ll sum = 0;
    ll cnt = 0;
    for(int i = 0; i < T.size(); i++) {
        ll a = 0;
        ll b = 0;
        ll c = 1e18;
        for(int j = 0; j < T[i].size(); j++) {
            if(T[i][j] == 'M') a++;
            else a--;
            if(j % 2) b = min(b, a);
            else c = min(c, a);
        }
        if(a >= 0) {
            if(sum + (cnt % 2? c : b) < 0) return false;
            if(X[i] > 1 && sum + a + ((cnt + (int)T[i].size()) % 2? c : b) < 0) return false;
            sum += a * X[i];
            cnt += X[i] * (int)T[i].size();
        }
        else {
            if(sum + a * (X[i] - 1) + ((cnt + (X[i] - 1) * (int)T[i].size()) % 2? c : b) < 0) return false;
            if(X[i] > 1 && sum + a * (X[i] - 2) + ((cnt + (X[i] - 2) * (int)T[i].size()) % 2? c : b) < 0) return false;
            sum += a * X[i];
            cnt += X[i] * (int)T[i].size();
        }
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(false);

    cin >> N >> M;

    for(int i = 0; i < M; i++) {
        cin >> S[i] >> K[i];

        int cnt = 0;
        for(int j = 0; j < S[i].size(); j++) {
            if(S[i][j] == 'M') cnt++;
        }
        msum += K[i] * cnt;
    }

    if(msum > N) {
        cout << -1;
        return 0;
    }

    ll s = 0, e = msum, p = -1;
    while(s <= e) {
        ll m = (s + e)>>1;

        if(check(m)) {
            p = m;
            e = m - 1;
        }
        else s = m + 1;
    }
    cout << p;
}

Compilation message (stderr)

toilets.cpp: In function 'void rem(char, char, ll)':
toilets.cpp:24:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < tt[i].size(); j++) if(tt[i][j] == c) cnt++;
                        ~~^~~~~~~~~~~~~~
toilets.cpp: In function 'void rev()':
toilets.cpp:74:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < T.size(); i++) {
                    ~~^~~~~~~~~~
toilets.cpp: In function 'bool check(ll)':
toilets.cpp:100:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < T.size(); i++) {
                    ~~^~~~~~~~~~
toilets.cpp:104:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < T[i].size(); j++) {
                        ~~^~~~~~~~~~~~~
toilets.cpp: In function 'int main()':
toilets.cpp:135:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < S[i].size(); j++) {
                        ~~^~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 22 / 22
• Subtask 3: 64 / 64