oj.uz

Submission #1111340

# Submission time Handle Problem Language Result Execution time Memory
1111340 2024-11-12T06:59:51 Z vjudge1 JJOOII 2 (JOI20_ho_t2) C++17
0 / 100
 1 ms 336 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pll pair<ll, ll>
ll n, k, pO[100001], pJ[100001], pI[100001], ans=1e18;
string str;
vector<ll> J, I;


int main(){
    cin >> n >> k;
    cin >> str;
    for(int i=1; i<=n; i++){
        if(str[i-1]=='J')
            J.push_back(i);
        if(str[i-1]=='I')
            I.push_back(i);
        if(str[i-1]=='O')pO[i]=pO[i-1]+1;
        else pO[i]=pO[i-1];
    }
    if(J.size()<k || I.size()<k || pO[n]<k){
        cout << -1 << endl;
        return 0;
    }
    for(int i=J.size()-1; i>=k-1; i--){
        int l=0, r=I.size()-1, mid, back=-1;
        while(l<=r){
            mid=(l+r)/2;
            if(pO[I[mid]+1]-pO[J[i]+1]<k){
                l=mid+1;
            }else{
                back=mid;
                r=mid-1;
            }
        }
        if(back==-1 || I.size() - back < k)continue;
        ans=min(ans, I[back+k]-J[i-k]+1-3*k);
    }
    cout << ans << endl;
}

Compilation message

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:23:16: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   23 |     if(J.size()<k || I.size()<k || pO[n]<k){
      |        ~~~~~~~~^~
ho_t2.cpp:23:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   23 |     if(J.size()<k || I.size()<k || pO[n]<k){
      |                      ~~~~~~~~^~
ho_t2.cpp:38:40: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   38 |         if(back==-1 || I.size() - back < k)continue;
      |                        ~~~~~~~~~~~~~~~~^~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -