Submission #443249

#	Time	Username	Problem	Language	Result	Execution time	Memory
443249		Fidisk	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	259 ms	72816 KiB

ho_t2

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

#define oo 1e15
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) (((xxxx)>>(aaaa-1))&1)

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<pair<int,int>,pair<int,int>> piiii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;
typedef pair<long double,long double> pld;
typedef pair<pair<long double,long double>,long double> plld;

const ll base=2e9+4257;
//const ll mod=1e9+7;
const ll mod2=1e9+4233;
const ld eps=1e-12;
const ll maxn=1e16;
const ld pi=acos(-1);
const ll delta=1e5+7;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};

int n,k,i,j,l,p,tp,res,nextp[200009][4][23];
string s;

int main(){
    IO;
    cin>>n>>k;
    res=n;
    cin>>s;
    s=" "+s;
    nextp[n][1][1]=n+1;
    nextp[n][2][1]=n+1;
    nextp[n][3][1]=n+1;
    nextp[n+1][1][1]=n+1;
    nextp[n+1][2][1]=n+1;
    nextp[n+1][3][1]=n+1;
    for (i=n;i>=1;i--) {
        for (j=1;j<=3;j++) {
            nextp[i-1][j][1]=nextp[i][j][1];
        }
        if (s[i]=='J') {
            nextp[i-1][1][1]=i;
        }
        else if (s[i]=='O') {
            nextp[i-1][2][1]=i;
        }
        else if (s[i]=='I') {
            nextp[i-1][3][1]=i;
        }
    }
    for (l=2;l<=20;l++) {
        for (j=1;j<=3;j++) {
            for (i=0;i<=n+1;i++) {
                //cout<<i<<' '<<j<<' '<<l<<' '<<nextp[i][j][l-1]<<' '<<nextp[nextp[i][j][l-1]][j][l-1]<<'\n';
                nextp[i][j][l]=nextp[nextp[i][j][l-1]][j][l-1];
            }
        }
    }
    //for (i=0;i<=n+1;i++) {
    //    for (j=1;j<=20;j++) {
    //        cout<<nextp[i][1][j]<<' ';
    //    }
    //    cout<<'\n';
    //}
    //cout<<nextp[1][1][2]<<'\n';
    //cout<<nextp[8][1][2]<<'\n';
    //cout<<nextp[1][1][3]<<'\n';
    k--;
    for (i=0;i<=n;i++) {
        p=nextp[i][1][1];
        tp=p;
        //cout<<p<<' ';
        for (j=20;j>=1;j--) {
            if (getbit(k,j)==1) {
                p=nextp[p][1][j];
            }
        }
        //cout<<p<<' ';
        p=nextp[p][2][1];
        //cout<<p<<' ';
        for (j=20;j>=1;j--) {
            if (getbit(k,j)==1) {
                p=nextp[p][2][j];
            }
        }
        //cout<<p<<' ';
        p=nextp[p][3][1];
        //cout<<p<<' ';
        for (j=20;j>=1;j--) {
            if (getbit(k,j)==1) {
                p=nextp[p][3][j];
            }
        }
        //cout<<p<<' ';
        //cout<<'\n';
        if (p!=n+1) {
            res=min(res,p-tp+1-(3*k+3));
        }
        //cout<<p<<' '<<tp<<'\n';
    }
    if (res==n) {
        cout<<-1;
        return 0;
    }
    cout<<res<<'\n';
}

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