Submission #337000

#	Time	Username	Problem	Language	Result	Execution time	Memory
337000		zggf	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	6 ms	3308 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;
string s;
vector<int> nxt1, nxt2, nxt3;

int sum = 0, wyn = 0;
int p1 = 0, p2 = 0, p3 = 0;
int k1 = 0, k2 = 0, k3 = 0;
bool pos = true;  

void push3(){
	p3 = nxt3[p3];
	k3 = nxt3[k3];
	if(p3==-1){
		pos = false;	
	}
}

void push2(){
	p2 = nxt2[p2];
	k2 = nxt2[k2];
	if(p2==-1){
		pos = false;	
	}
}

void push1(){
	p1 = nxt1[p1];
	k1 = nxt1[k1];
	if(p1==-1){
		pos = false;	
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
	int n, k; cin>>n>>k;
	nxt1.resize(n, -1);
	nxt2.resize(n, -1);
	nxt3.resize(n, -1);
	cin>>s;

	for(int i = n-1; i > 0; i--){
		nxt1[i-1] = nxt1[i];
		nxt2[i-1] = nxt2[i];
		nxt3[i-1] = nxt3[i];
		switch(s[i]){
			case 'J':
				nxt1[i-1] = i;
				break;	
			case 'O':
				nxt2[i-1] = i;
				break;	
			case 'I':
				nxt3[i-1] = i;
				break;	
		}	
	}
	
	p1 = nxt1[0];
	p2 = nxt2[0];
	p3 = nxt3[0];
	k1 = nxt1[0];
	k2 = nxt2[0];
	k3 = nxt3[0];
	switch(s[0]){
		case 'J':
			p1 = 0;
			k1= 0;
			break;	
		case 'O':
			p2 = 0;
			k2= 0;
			break;	
		case 'I':
			p3 = 0;
			k3= 0;
			break;	
	}	

	for(int i = 0; i < k-1; i++){
		p1 = nxt1[p1];	
		p2 = nxt2[p2];	
		p3 = nxt3[p3];	
		if(p1==-1) {cout<<-1; return 0;}
		if(p2==-1) {cout<<-1; return 0;}
		if(p3==-1) {cout<<-1; return 0;}
	}

	while(p1>k2){
		push2();
		if(!pos) {cout<<-1; return 0;}	
	}	
	while(p2>k3){
		push3();
		if(!pos) {cout<<-1; return 0;}	
	}	

	int wyn = p3-k1;	

	while(pos){
		push1();
		while(p1>k2){
			push2();
			if(!pos) {break;}	
		}	
		while(p2>k3){
			push3();
			if(!pos) {break;}	
		}	
		if(pos) wyn = min(wyn, p3-k1);
	}
	
	cout<<wyn+1-3*k;
	return 0;	
}

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