Submission #229946

#	Time	Username	Problem	Language	Result	Execution time	Memory
229946		grt	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	12 ms	3380 KiB

ho_t2

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 200*1000+10,INF = 1e9 +10;
int n,k;
string s;
vi posJ, posO, posI;
int nxtJ[nax], nxtI[nax];

int main() {_
	cin >> n >> k >> s;
	for(int i = 0; i < n; ++i) {
		if(s[i] == 'J') posJ.PB(i);
		if(posJ.size() < k) {
			nxtJ[i] = -1;
		} else {
			nxtJ[i] = posJ[(int)posJ.size() - k];
		}
	}
	for(int i = n-1; i >=0; --i) {
		if(s[i] == 'I') posI.PB(i);
		if(posI.size() < k) {
			nxtI[i] = -1;
		} else {
			nxtI[i] = posI[(int)posI.size()-k];
		}
	}
	int l = 0;
	int cntO = 0;
	int ans = INF;
	for(int r = 0; r < n; ++r) {
		if(s[r] == 'O') cntO++;
		while(cntO - (s[l] == 'O') >= k) {
			if(s[l] == 'O') cntO--;
			l++;
		}
		if(cntO == k) {
			int a = nxtJ[l], b = nxtI[r];
			//cout << a << " " << l << " " << r << " " << b << "\n";
			if(a == -1 || b == -1) continue;
			ans = min(ans,b-a+1 - 3*k);
		}
	}
	if(ans == INF) {
		cout << "-1";
	} else {
		cout << ans;
	}
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(posJ.size() < k) {
      ~~~~~~~~~~~~^~~
ho_t2.cpp:32:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(posI.size() < k) {
      ~~~~~~~~~~~~^~~

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