oj.uz

답안 #716237

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
716237 2023-03-29T10:54:22 Z hpesoj JJOOII 2 (JOI20_ho_t2) C++17
100 / 100
 8 ms 4024 KB 
#include <bits/stdc++.h>
//#define int long long
#define pi pair <int, int>
#define ppi pair <pi, int>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << '\n'
#define debug2(x, y) cout << #x << ": " << x << ' ' << #y << ": " << y << '\n'
#define debug3(x, y, z) cout << #x << ": " << x << ' ' << #y << ": " << y << ' ' << #z << ": " << z << '\n'
#define debug4(x, y, z, w) cout << #x << ": " << x << ' ' << #y << ": " << y << ' ' << #z << ": " << z << ' ' << #w << ": " << w << '\n'
using namespace std;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const int inf = 1000000000;
int n, k, JJ, OO, II;
string s;
vector <int> J, O, I;
int ans = inf, nearestj[300005], nearesto[300005], nearesti[300005];
int nearest(char x, int i){
	if(x == 'J'){
		if(i + k - 1 >= JJ) return inf;
		else return J[i+k-1];
	}
	else if(x == 'O'){
		if(i + k - 1 >= OO) return inf;
		else return O[i+k-1];
	}
	else{
		if(i + k - 1 >= II) return inf;
		else return I[i+k-1];
	}
}
signed main(){
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k >> s;
	for(int i = 0; i < n; i++){
		if(s[i] == 'J') J.pb(i);
		else if(s[i] == 'O') O.pb(i);
		else I.pb(i);
	}
	JJ = J.size(), OO = O.size(); II = I.size();
	int i = 0;
	for(int j = 0; j < JJ; j++){
		int x = nearest('J', j);
		for(; i <= J[j]; i++) nearestj[i] = x;
	}
	for(; i <= n; i++) nearestj[i] = inf;
	i = 0;
	for(int j = 0; j < OO; j++){
		int x = nearest('O', j);
		for(; i <= O[j]; i++) nearesto[i] = x;
	}
	for(; i <= n; i++) nearesto[i] = inf;
	i = 0;
	for(int j = 0; j < II; j++){
		int x = nearest('I', j);
		for(; i <= I[j]; i++) nearesti[i] = x;
	}
	for(; i <= n; i++) nearesti[i] = inf;
	//for(int i = 0; i < n; i++) cout << nearestj[i] << ' ' << nearesto[i] << ' ' << nearesti[i] << '\n';
	for(i = 0; i < JJ; i++){
		int r1 = nearestj[J[i]];
		int r2 = (r1 == inf ? inf : nearesto[r1+1]);
		int r3 = (r2 == inf ? inf : nearesti[r2+1]);
		//debug4(J[i], r1, r2, r3);
		if(r3 == inf) continue;
		ans = min(ans, r3-J[i]+1 - 3 * k);
	}
	cout << (ans == inf ? -1 : ans);
}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 0 ms 340 KB Output is correct
34 Correct 0 ms 340 KB Output is correct
35 Correct 0 ms 340 KB Output is correct

Subtask #3
87.0 / 87.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 0 ms 340 KB Output is correct
34 Correct 0 ms 340 KB Output is correct
35 Correct 0 ms 340 KB Output is correct
36 Correct 6 ms 3664 KB Output is correct
37 Correct 7 ms 3992 KB Output is correct
38 Correct 8 ms 3864 KB Output is correct
39 Correct 7 ms 3824 KB Output is correct
40 Correct 7 ms 3916 KB Output is correct
41 Correct 7 ms 3812 KB Output is correct
42 Correct 8 ms 4024 KB Output is correct
43 Correct 4 ms 2544 KB Output is correct
44 Correct 6 ms 3160 KB Output is correct
45 Correct 7 ms 3972 KB Output is correct
46 Correct 7 ms 3908 KB Output is correct
47 Correct 7 ms 3844 KB Output is correct
48 Correct 7 ms 3920 KB Output is correct
49 Correct 5 ms 2776 KB Output is correct
50 Correct 7 ms 3904 KB Output is correct
51 Correct 7 ms 3916 KB Output is correct
52 Correct 7 ms 3672 KB Output is correct
53 Correct 7 ms 3908 KB Output is correct
54 Correct 4 ms 3808 KB Output is correct
55 Correct 4 ms 3812 KB Output is correct
56 Correct 4 ms 3808 KB Output is correct