Submission #717588

#	Time	Username	Problem	Language	Result	Execution time	Memory
717588		vjudge1	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	23 ms	3068 KiB

ho_t2

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
int a[200001];
int b[200001];
vector<int> x, y, z;

int main() {
    // Write C++ code here
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        char c;
        cin >> c;
        a[i] = c;
        a[i] -= 72;
        if(a[i] == 2)x.push_back(i);
        if(a[i] == 7)y.push_back(i);
        if(a[i] == 1)z.push_back(i);
    }
    int t = 1;
    int h = 0;
    while(t <= n && h < m){
        if(a[t] == 2)h++;
        t++;
    }
    if(h < m){
        cout << "-1";
        return 0;
    }
    h = 0;
    while(t <= n && h < m){
        if(a[t] == 7)h++;
        t++;
    }
    if(h < m){
        cout << "-1";
        return 0;
    }
    h = 0;
    while(t <= n && h < m){
        if(a[t] == 1)h++;
        t++;
    }
    if(h < m){
        cout << "-1";
        return 0;
    }
    int x_ = 0, y_ = 0, z_ = 0;
    for(int i = 1; i <= n; i++){
        if(a[i] == 2){
            if(x.size() > x_ + m - 1){
                b[i] = x[x_+m-1];
            }
            x_++;
        }
        if(a[i] == 7){
            if(y.size() > y_ + m - 1){
                b[i] = y[y_+m-1];
            }
            y_++;
        }
        if(a[i] == 1){
            if(z.size() > z_ + m - 1){
                b[i] = z[z_+m-1];
            }
            z_++;
        }
    }
    h = 0;
    for(int i = 0; b[y[i]]; i++){
        while(h < z.size() && z[h] <= b[y[i]])h++;
        if(h == z.size())b[y[i]] = 0;
        else b[y[i]] = b[z[h]];
    }
    h = 0;
    t = INT_MAX;
    for(int i = 0; b[x[i]]; i++){
        while(h < y.size() && y[h] <= b[x[i]])h++;
        if(h == y.size())b[x[i]] = 0;
        else b[x[i]] = b[y[h]];
        if(b[x[i]]){
            t = min(t, b[x[i]] - x[i] + 1 - 3 * m);
        }
    }
    cout << t;

    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:52:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |             if(x.size() > x_ + m - 1){
      |                ~~~~~~~~~^~~~~~~~~~~~
ho_t2.cpp:58:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |             if(y.size() > y_ + m - 1){
      |                ~~~~~~~~~^~~~~~~~~~~~
ho_t2.cpp:64:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |             if(z.size() > z_ + m - 1){
      |                ~~~~~~~~~^~~~~~~~~~~~
ho_t2.cpp:72:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         while(h < z.size() && z[h] <= b[y[i]])h++;
      |               ~~^~~~~~~~~~
ho_t2.cpp:73:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         if(h == z.size())b[y[i]] = 0;
      |            ~~^~~~~~~~~~~
ho_t2.cpp:79:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         while(h < y.size() && y[h] <= b[x[i]])h++;
      |               ~~^~~~~~~~~~
ho_t2.cpp:80:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         if(h == y.size())b[x[i]] = 0;
      |            ~~^~~~~~~~~~~

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