Submission #1015373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015373		snpmrnhlol	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	14 ms	4944 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5;
const int inf = 2e9;
char v[N];
vector <int> occ[3];
int nxt[N + 1][3];
int tr[N];
int main(){
    int n,k;
    int ans = inf;
    cin>>n>>k;
    for(int i = 0;i < n;i++){
        cin>>v[i];
        if(v[i] == 'J')v[i] = 0;
        else if(v[i] == 'O')v[i] = 1;
        else v[i] = 2;
        occ[v[i]].push_back(i);
        tr[i] = occ[v[i]].size() - 1;
    }
    nxt[n][0] = nxt[n][1] = nxt[n][2] = n;
    for(int i = n - 1;i >= 0;i--){
        for(int j = 0;j < 3;j++){
            nxt[i][j] = nxt[i + 1][j];
        }
        nxt[i][v[i]] = i;
        //cout<<nxt[i][0]<<' '<<nxt[i][1]<<' '<<nxt[i][2]<<'\n';
    }
    for(int i = 0;i < n;i++){
        int pos = nxt[i][0];
        if(pos == n || occ[0].size() < tr[pos] + k)continue;
        int pos1 = occ[0][tr[pos] + k - 1];
        int id1 = nxt[pos1][1];
        if(id1 == n || occ[1].size() < tr[id1] + k)continue;
        int pos2 = occ[1][tr[id1] + k - 1];
        int id2 = nxt[pos2][2];
        if(id2 == n || occ[2].size() < tr[id2] + k)continue;
        int pos3 = occ[2][tr[id2] + k - 1];
        ///i -> pos3
        ans = min(ans,n - 3*k - (n - 1 - pos3) - (i - 0));
    }
    if(ans == inf)ans = -1;
    cout<<ans<<'\n';
    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:18:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   18 |         occ[v[i]].push_back(i);
      |             ~~~^
ho_t2.cpp:19:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   19 |         tr[i] = occ[v[i]].size() - 1;
      |                     ~~~^
ho_t2.cpp:26:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   26 |         nxt[i][v[i]] = i;
      |                ~~~^
ho_t2.cpp:31:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |         if(pos == n || occ[0].size() < tr[pos] + k)continue;
      |                        ~~~~~~~~~~~~~~^~~~~~~~~~~~~
ho_t2.cpp:34:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |         if(id1 == n || occ[1].size() < tr[id1] + k)continue;
      |                        ~~~~~~~~~~~~~~^~~~~~~~~~~~~
ho_t2.cpp:37:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |         if(id2 == n || occ[2].size() < tr[id2] + k)continue;
      |                        ~~~~~~~~~~~~~~^~~~~~~~~~~~~

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