Submission #286667

#	Time	Username	Problem	Language	Result	Execution time	Memory
286667		leductoan	JJOOII 2 (JOI20_ho_t2)	C++14	13 / 100	6 ms	5204 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
#define task "JOI20_ho_t2"
#define lb lower_bound
#define ub upper_bound
#define ALL(v) (v).begin(),(v).end()
#define zs(v) (int)(v).size()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define cntbit __builtin_popcountll
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
const ll mod=1000000007; /// 998244353
const int base=311;
const int N=1e5+5;

int n,k,f[N][5];
string s;

void biot()
{
    cin>>n>>k;
    cin>>s;
    s=' '+s;
    int l=1;
    string t="JOI";
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<3;++j)
        {
            f[i][j]=f[i-1][j]+(s[i]==t[j]);
        }
    }
    int ans=1e9;
    for(int i=1;i<=n;++i)
    {
        int l=i, r=n, j=-1, o=-1, ii=-1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(f[mid][0]-f[i-1][0]>=k) r=mid-1, j=mid;
            else l=mid+1;
        }
        if(j==-1) continue;
        l=j+1, r=n;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(f[mid][1]-f[j][1]>=k) r=mid-1, o=mid;
            else l=mid+1;
        }
        if(o==-1) continue;
        l=o+1, r=n;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(f[mid][2]-f[o][2]>=k) r=mid-1, ii=mid;
            else l=mid+1;
        }
        if(ii!=-1) ans=min(ans,ii-i+1-k*3);
    }
    cout<<(ans==1e9?-1:ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    biot();
}

Compilation message (stderr)

ho_t2.cpp: In function 'void biot()':
ho_t2.cpp:30:9: warning: unused variable 'l' [-Wunused-variable]
   30 |     int l=1;
      |         ^
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   74 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
ho_t2.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   75 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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