Submission #258668

#	Time	Username	Problem	Language	Result	Execution time	Memory
258668		Molukhyyeh	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	26 ms	9224 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end() 

int const N = 200001;
int n, k, c0[N], c1[N], c2[N], ad[N];
vector<int> g[N];

int main(){
    string s; 
    scanf("%d%d", &n, &k);
    cin >> s;
    int an = 1e9, f = -1; 
    for(int i = 0; i<n; ++i){
    	c0[i] = (s[i] != 'J');
    	c1[i] = (s[i] != 'O');
    	c2[i] = (s[i] != 'I');
    	g[s[i]].push_back(i);
    	if(i)c0[i] += c0[i-1], c1[i] += c1[i-1], c2[i] += c2[i-1];
    }
    for(int i = 0; i<g['J'].size()-k+1; ++i){
        int l = g['J'][i], r = g['J'][i+k-1];
        int rem = r-l+1 - k;
        int it = lower_bound(all(g['O']), r)-g['O'].begin();
        if(it == g['O'].size() || it+k > g['O'].size())break;
        int itr = g['O'][it+k-1];
        it = g['O'][it];
        rem += (it-r-1)+(itr-it+1-k); 
        int ii = lower_bound(all(g['I']), itr)-g['I'].begin();
        if(ii == g['I'].size() || ii+k > g['I'].size())break;
        int iir = g['I'][ii+k-1];
        ii = g['I'][ii];
        rem += (ii-itr-1)+(iir-ii+1-k);
        an = min(an, rem);
        f = 1; 
    }
    printf("%d\n", ~f? an: -1);
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:19:12: warning: array subscript has type 'char' [-Wchar-subscripts]
      g[s[i]].push_back(i);
            ^
ho_t2.cpp:22:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i<g['J'].size()-k+1; ++i){
                    ~^~~~~~~~~~~~~~~~~~
ho_t2.cpp:26:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(it == g['O'].size() || it+k > g['O'].size())break;
            ~~~^~~~~~~~~~~~~~~~
ho_t2.cpp:26:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(it == g['O'].size() || it+k > g['O'].size())break;
                                   ~~~~~^~~~~~~~~~~~~~~
ho_t2.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ii == g['I'].size() || ii+k > g['I'].size())break;
            ~~~^~~~~~~~~~~~~~~~
ho_t2.cpp:31:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ii == g['I'].size() || ii+k > g['I'].size())break;
                                   ~~~~~^~~~~~~~~~~~~~~
ho_t2.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~

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