Submission #903228

#	Time	Username	Problem	Language	Result	Execution time	Memory
903228		yellowtoad	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	22 ms	2136 KiB

ho_t2

#include <iostream>
#include <vector>
using namespace std;

int n, k, l, r, mid, minn = 1e9, pos;
char c[200010];
vector<int> v[200];

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
		v[c[i]].push_back(i);
	}
	for (int i = 1; i <= n; i++) {
		if (c[i] == 'J') {
			l = 0; r = (int)v['J'].size()-1;
			while (l <= r) {
				mid = (l+r)/2;
				if (v['J'][mid] < i) l = mid+1;
				else r = mid-1;
			}
			l += k-1;
			if (l >= v['J'].size()) continue;
			pos = v['J'][l];
			l = 0; r = (int)v['O'].size()-1;
			while (l <= r) {
				mid = (l+r)/2;
				if (v['O'][mid] < pos) l = mid+1;
				else r = mid-1;
			}
			l += k-1;
			if (l >= v['O'].size()) continue;
			pos = v['O'][l];
			l = 0; r = (int)v['I'].size()-1;
			while (l <= r) {
				mid = (l+r)/2;
				if (v['I'][mid] < pos) l = mid+1;
				else r = mid-1;
			}
			l += k-1;
			if (l >= v['I'].size()) continue;
			pos = v['I'][l];
			minn = min(minn,pos-i+1-k*3);
		}
	}
	if (minn == 1e9) cout << -1 << endl;
	else cout << minn << endl;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:13:8: warning: array subscript has type 'char' [-Wchar-subscripts]
   13 |   v[c[i]].push_back(i);
      |     ~~~^
ho_t2.cpp:24:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |    if (l >= v['J'].size()) continue;
      |        ~~^~~~~~~~~~~~~~~~
ho_t2.cpp:33:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    if (l >= v['O'].size()) continue;
      |        ~~^~~~~~~~~~~~~~~~
ho_t2.cpp:42:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    if (l >= v['I'].size()) continue;
      |        ~~^~~~~~~~~~~~~~~~

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