Submission #754008

#	Time	Username	Problem	Language	Result	Execution time	Memory
754008		vjudge1	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	19 ms	5684 KiB

ho_t2

/**
  * Author: Amirrrr
  * Created: 06.06.2023
  * Why am I so stupid? :c
  * Slishkom slab
**/

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define FF first
#define SS second
#define ent "\n"
#define int long long

const int N = 1e6 + 13;
const int MOD = 1e9 + 7;
const int INF = 1e18;

int n,k,pref[N],pref1[N],pref2[N];
string s;

void gogo (){
    cin>>n>>k;
    cin>>s;
    s='+'+s;
    int mn = INF;
    for (int i = 1 ; i <= n ; i ++){
        if (s[i] =='J')pref[i]++;
        if(s[i]=='O')pref1[i]++;
        if(s[i]=='I')pref2[i]++;
        pref[i]+=pref[i-1],pref1[i]+=pref1[i-1],pref2[i]+=pref2[i-1];
    }
    for(int i = 1 ; i <= n ; i ++){
        if(s[i]!='J') continue;
        int l=i,r=n,ans=-1,ans1=-1,ans2=-1;
        while(l<=r){
            int mid=(l+r)>>1;
            if(pref[mid] - pref[i-1]==k){
                ans=mid;
                r=mid-1;
            }
            else if (pref[mid] - pref[i-1] > k){
                r = mid-1;
            }
            else l = mid + 1;
        }
        l=ans+1,r=n;
        while(l<=r){
            int mid=(l+r)>>1;
            if(pref1[mid] - pref1[ans]==k){
                ans1=mid;
                r=mid-1;
            }
            else if (pref1[mid] - pref1[ans] > k){
                r = mid-1;
            }
            else l = mid + 1;
        }
        l=ans1+1,r=n;
        while(l<=r){
            int mid=(l+r)>>1;
            if(pref2[mid]-pref2[ans1]==k){
                ans2=mid;
                r=mid-1;
            }
            else if (pref2[mid]-pref2[ans1]>k){
                r=mid-1;
            }
            else l=mid + 1;
        }
        if(ans2==-1 || ans==-1 || ans1==-1){
            continue;
        }
        mn = min(mn, ans2 - i + 1 - 3 * k);
    }
    if(mn!=INF)cout<< mn;
    else cout<<-1;
}

signed main (/*Amir Mirmanov*/){
    ios_base::sync_with_stdio(0), cin.tie(0);
    int Q = 1,test = 1;
    //freopen("herding.in","r",stdin);
	//freopen("herding.out","w",stdout);
    //cin >> Q;
    while (Q --){
        gogo ();
    }
    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:86:15: warning: unused variable 'test' [-Wunused-variable]
   86 |     int Q = 1,test = 1;
      |               ^~~~

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