답안 #337000

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
337000 2020-12-17T19:53:35 Z zggf JJOOII 2 (JOI20_ho_t2) C++14
100 / 100
6 ms 3308 KB
#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;	
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 492 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 1 ms 364 KB Output is correct
33 Correct 1 ms 364 KB Output is correct
34 Correct 1 ms 364 KB Output is correct
35 Correct 1 ms 364 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 492 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 1 ms 364 KB Output is correct
33 Correct 1 ms 364 KB Output is correct
34 Correct 1 ms 364 KB Output is correct
35 Correct 1 ms 364 KB Output is correct
36 Correct 6 ms 3064 KB Output is correct
37 Correct 6 ms 3308 KB Output is correct
38 Correct 6 ms 3308 KB Output is correct
39 Correct 6 ms 3192 KB Output is correct
40 Correct 5 ms 3308 KB Output is correct
41 Correct 5 ms 3308 KB Output is correct
42 Correct 6 ms 3308 KB Output is correct
43 Correct 4 ms 2348 KB Output is correct
44 Correct 4 ms 2668 KB Output is correct
45 Correct 5 ms 3308 KB Output is correct
46 Correct 5 ms 3308 KB Output is correct
47 Correct 5 ms 3308 KB Output is correct
48 Correct 5 ms 3308 KB Output is correct
49 Correct 5 ms 2412 KB Output is correct
50 Correct 5 ms 3308 KB Output is correct
51 Correct 5 ms 3308 KB Output is correct
52 Correct 4 ms 3180 KB Output is correct
53 Correct 5 ms 3308 KB Output is correct
54 Correct 4 ms 3308 KB Output is correct
55 Correct 4 ms 3308 KB Output is correct
56 Correct 4 ms 3308 KB Output is correct