Submission #1114696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114696		tkwiatkowski	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	2069 ms	336 KiB

ho_t2

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <string>

using namespace std;

typedef long long ll;

struct litter {
    ll prej;
    ll postj;
    ll preo;
    ll posto;
    ll prei;
    ll posti;
    litter(ll postj, ll posto, ll posti) : prej(0), preo(0), prei(0), postj(postj), posto(posto), posti(posti) {
    };
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string s;
    ll sn, k;
    cin >> sn >> k >> s;
    int p, e;
    p = s.find_first_of('J');
    e = s.find_last_of('I');
    s = s.substr(p, e - p + 1);
    ll n = s.size();
    ll ilej = 0, ileo = 0, ilei = 0;
    for(char c : s) {
        if(c == 'J') ilej++;
        if(c == 'O') ileo++;
        if(c == 'I') ilei++;
    }
    //cout << ilej << " " << ileo << " " << ilei << '\n';
    vector<litter> litterki(n, litter(ilej, ileo, ilei));
    //cout << s << '\n';
    for(int i = 0; i < n; i++) {
        char c = s[i];
        if(i != 0) {
        litterki[i].prej=litterki[i - 1].prej;
        litterki[i].postj=litterki[i - 1].postj;
        litterki[i].preo=litterki[i - 1].preo;
        litterki[i].posto=litterki[i - 1].posto;
        litterki[i].prei=litterki[i - 1].prei;
        litterki[i].posti=litterki[i - 1].posti;
        }
        if(c == 'J') {litterki[i].prej+=1;litterki[i].postj =  ilej - litterki[i].prej;}
        if(c == 'O') {litterki[i].preo+=1;litterki[i].posto =  ileo - litterki[i].preo;}
        if(c == 'I') {litterki[i].prei+=1;litterki[i].posti =  ilei - litterki[i].prei;}
    }
    // for(int i = 0; i < n; i++) {
    //     cout << litterki[i].prej << " " << litterki[i].postj << " " << litterki[i].preo << " " << litterki[i].posto << " " << litterki[i].prei << " " << litterki[i].posti << '\n';
    // }
    string cel = "";
    for(int i = 0; i < k; i++) {
        cel += "J";
    }
    for(int i = 0; i < k; i++) {
        cel += "O";
    }
    for(int i = 0; i < k; i++) {
        cel += "I";
    }
    ll il = 0;
    while(s != cel && n > cel.size()) {
        vector<bool> cz(n, false);
        for(int i = n - 1; i >= 0; i--) {
            char c = s[i];
            if (c == 'J') {
                litter l = litterki[i];
                //cout << "J" << l.posto << " " << l.posti << '\n';
                if(l.posto >= k && l.posti >= k) {
                    cz[i] = true;
                }
            }
            if (c == 'O') {
                litter l = litterki[i];
                //cout << "J" << l.prej << " " << l.posti << '\n';
                if(l.prej >= k && l.posti >= k) {
                    cz[i] = true;
                }
            }
            if (c == 'I') {
                litter l = litterki[i];
                //cout << "J" << l.preo << " " << l.prej << '\n';
                if(l.prej >= k && l.preo >= k) {
                    cz[i] = true;
                }
            }
        }
        int lt = -1;
        for(int i = 0;i < n; i++) {
            if(cz[i]) lt = i;
        }
        if(lt < 0) {cout << -1;return 0;}
        string sp = "";
        for(int i = 0; i < n; i++) {
            if(cz[i]) {
                sp += s[i];
            } else {
                if(sp == "") {
                    il++;
                } else if(i < lt) {
                    il++;
                }
            }
        }
        s = sp;
        n = s.size();
    }
    //cout << s << " " << il << "\n";
    if(cel == s) {
        cout << il;
    } else {
        cout << "-1";
    }

}

Compilation message (stderr)

ho_t2.cpp: In constructor 'litter::litter(ll, ll, ll)':
ho_t2.cpp:18:8: warning: 'litter::prei' will be initialized after [-Wreorder]
   18 |     ll prei;
      |        ^~~~
ho_t2.cpp:15:8: warning:   'll litter::postj' [-Wreorder]
   15 |     ll postj;
      |        ^~~~~
ho_t2.cpp:20:5: warning:   when initialized here [-Wreorder]
   20 |     litter(ll postj, ll posto, ll posti) : prej(0), preo(0), prei(0), postj(postj), posto(posto), posti(posti) {
      |     ^~~~~~
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:73:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     while(s != cel && n > cel.size()) {
      |                       ~~^~~~~~~~~~~~

• Subtask 1: 0 / 1
• Subtask 2: 0 / 12
• Subtask 3: 0 / 87