oj.uz

Submission #981364

# Submission time Handle Problem Language Result Execution time Memory
981364 2024-05-13T05:55:03 Z Amaarsaa JJOOII 2 (JOI20_ho_t2) C++14
100 / 100
 12 ms 3812 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long ;
int J[200004], I[200004];
int main() {
//	freopen("moocast.in", "r", stdin);
//	freopen("moocast.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll t, n, m, ans,l, s, lo, hi, mid, sum, x, y, r, p, i, j;

	cin >> n >> m;
	
	string str;
	
	cin >> str;
	
	str = "." + str;
	vector < ll > O;
	for (i =1; i <= n; i ++) {
		J[i] = J[i - 1];
		I[i] = I[i - 1];
		if ( str[i] == 'I') I[i]++;
		if ( str[i] == 'J') J[i] ++;
		if ( str[i] == 'O') O.push_back(i);
	}
	ans = -1;
	for (i = m - 1; i < O.size(); i ++) {
		l = O[i - m + 1];
		r = O[i];
		if ( I[n] - I[r - 1] < m || J[l] < m) continue;
		lo = 1;
		hi = l;
		ll door, deer;
		while ( lo < hi) {
			mid = (lo +hi)/2;
		//	cout << lo << " " << hi << endl;
			if ( J[l] - J[mid - 1] >= m) lo = mid + 1;
			else hi =mid;
		}
		door = lo - 1;
		lo = r;
		hi = n;
		while ( lo < hi) {
			mid = (lo +hi)/2;
			if ( I[mid] - I[r - 1] < m) lo = mid + 1;
			else hi =mid;
		}
		deer = lo;
		p = (deer - door + 1 - 3 * m);
		if ( ans == -1) ans = p;
		else ans = min(ans, p);
	}
	cout << ans << endl;
}

Compilation message

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:29:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for (i = m - 1; i < O.size(); i ++) {
      |                  ~~^~~~~~~~~~
ho_t2.cpp:11:5: warning: unused variable 't' [-Wunused-variable]
   11 |  ll t, n, m, ans,l, s, lo, hi, mid, sum, x, y, r, p, i, j;
      |     ^
ho_t2.cpp:11:21: warning: unused variable 's' [-Wunused-variable]
   11 |  ll t, n, m, ans,l, s, lo, hi, mid, sum, x, y, r, p, i, j;
      |                     ^
ho_t2.cpp:11:37: warning: unused variable 'sum' [-Wunused-variable]
   11 |  ll t, n, m, ans,l, s, lo, hi, mid, sum, x, y, r, p, i, j;
      |                                     ^~~
ho_t2.cpp:11:42: warning: unused variable 'x' [-Wunused-variable]
   11 |  ll t, n, m, ans,l, s, lo, hi, mid, sum, x, y, r, p, i, j;
      |                                          ^
ho_t2.cpp:11:45: warning: unused variable 'y' [-Wunused-variable]
   11 |  ll t, n, m, ans,l, s, lo, hi, mid, sum, x, y, r, p, i, j;
      |                                             ^
ho_t2.cpp:11:57: warning: unused variable 'j' [-Wunused-variable]
   11 |  ll t, n, m, ans,l, s, lo, hi, mid, sum, x, y, r, p, i, j;
      |                                                         ^

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 464 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 464 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 600 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 356 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct

Subtask #3
87.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 464 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 600 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 356 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 7 ms 2860 KB Output is correct
37 Correct 8 ms 3616 KB Output is correct
38 Correct 8 ms 3612 KB Output is correct
39 Correct 9 ms 3616 KB Output is correct
40 Correct 5 ms 3616 KB Output is correct
41 Correct 8 ms 3616 KB Output is correct
42 Correct 11 ms 3508 KB Output is correct
43 Correct 2 ms 2392 KB Output is correct
44 Correct 3 ms 2636 KB Output is correct
45 Correct 3 ms 3616 KB Output is correct
46 Correct 4 ms 3812 KB Output is correct
47 Correct 3 ms 3616 KB Output is correct
48 Correct 3 ms 3616 KB Output is correct
49 Correct 2 ms 2148 KB Output is correct
50 Correct 3 ms 3616 KB Output is correct
51 Correct 4 ms 3612 KB Output is correct
52 Correct 3 ms 3112 KB Output is correct
53 Correct 4 ms 3616 KB Output is correct
54 Correct 12 ms 3356 KB Output is correct
55 Correct 5 ms 3100 KB Output is correct
56 Correct 3 ms 3104 KB Output is correct