Submission #757082

#	Time	Username	Problem	Language	Result	Execution time	Memory
757082		michao	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	24 ms	5416 KiB

ho_t2

#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAX=2e5+5;
const int inf=(int)1e18+9;
int pref[MAX][3];
char s[MAX];
int ans=inf;
int getnum(char x){
  if (x=='J')return 0;
  if (x=='O')return 1;
  if (x=='I')return 2;
  assert(false);
  return -1;
}
int n,k;

int ile(int l,int r,int id){
  return pref[r][id]-pref[l-1][id];
}

int check(int lefty){
  int l=lefty;
  for (int i=0;i<3;i++){
    if (l>n)return inf;
    if (ile(l,n,i)<k)return inf;
    int ip=l-1,ik=n;
    while (ip+1<ik){
      int mid=(ip+ik)>>1;
      if (ile(l,mid,i)>=k)ik=mid;
      else ip=mid;
    }
    if (i<2)
    l=ik+1;
    else l=ik;
  }
  return l-lefty+1-k*3;
}
int32_t main()
{
  BOOST;
  cin>>n>>k;
  for (int i=1;i<=n;i++)cin>>s[i];
  for (int i=1;i<=n;i++){
    for (int j=0;j<3;j++)pref[i][j]=pref[i-1][j]+(getnum(s[i])==j);
  }
  for (int i=1;i<=n;i++){
    if (s[i]=='J'){
      ans=min(ans,check(i));
    }
  }
  if (ans==inf)ans=-1;
  cout<<ans;
  return 0;
}

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