Submission #288777

#	Time	Username	Problem	Language	Result	Execution time	Memory
288777		luciocf	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	128 ms	2048 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9+10;

int n, k;
vector<int> pos[3];

int get_next(int ind, int p)
{
	auto it = lower_bound(pos[ind].begin(), pos[ind].end(), p);
	if (it == pos[ind].end()) return -1;

	int x = (int)(it-pos[ind].begin());

	if (x+k-1 >= pos[ind].size()) return -1;

	return pos[ind][x+k-1];
}

bool ok(int i)
{
	if (i+k-1 >= pos[0].size()) return false;

	int p = pos[0][i+k-1];

	p = get_next(1, p+1);
	if (p == -1) return false;

	p = get_next(2, p+1);
	if (p == -1) return false;

	return true;
}

int main(void)
{
	string s;

	cin >> n >> k >> s;

	int ans = inf;

	for (int i = 0; i < n; i++)
	{
		if (s[i] == 'J') pos[0].push_back(i);
		else if (s[i] == 'O') pos[1].push_back(i);
		else pos[2].push_back(i);

		if (s[i] != 'I' || pos[0].size() < k) continue;

		int ini = 0, fim = pos[0].size()-1, opt = -1;

		while (ini <= fim)
		{
			int mid = (ini+fim)>>1;

			if (ok(mid)) opt = mid, ini = mid+1;
			else fim = mid-1;
		}

		if (opt != -1)
			ans = min(ans, i-pos[0][opt]+1-3*k);
	}

	if (ans != inf) cout << ans << "\n";
	else cout << "-1\n";
}

Compilation message (stderr)

ho_t2.cpp: In function 'int get_next(int, int)':
ho_t2.cpp:17:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  if (x+k-1 >= pos[ind].size()) return -1;
      |      ~~~~~~^~~~~~~~~~~~~~~~~~
ho_t2.cpp: In function 'bool ok(int)':
ho_t2.cpp:24:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  if (i+k-1 >= pos[0].size()) return false;
      |      ~~~~~~^~~~~~~~~~~~~~~~
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:51:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |   if (s[i] != 'I' || pos[0].size() < k) continue;
      |                      ~~~~~~~~~~~~~~^~~

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