Submission #981364

#	Time	Username	Problem	Language	Result	Execution time	Memory
981364		Amaarsaa	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	12 ms	3812 KiB

ho_t2

#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 (stderr)

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 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87