Submission #260830

#	Time	Username	Problem	Language	Result	Execution time	Memory
260830		sahil_k	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	30 ms	2560 KiB

ho_t2

#include <iostream>
#include <deque>
using namespace std;
#define MAXN 200005
int n, k;
char s[MAXN];
int last[MAXN];
int temp[MAXN];
deque<int> dq;
int prv;
int main () {
	cin >> n >> k;
	for (int i=0; i<n; i++) {
		cin >> s[i];
		if (s[i] == 'I') last[i] = i;
	}
	for (int i=n-1; i>=0; i--) {
		if (s[i] != 'I') continue;
		dq.push_front(i);
		if (dq.size() > k) dq.pop_back();
		if (dq.size() == k) {
			temp[i] = last[dq.back()];
		} else {
			temp[i] = 1e8;
		}
	}
	for (int i=0; i<n; i++) last[i] = temp[i];
	prv = -1;
	for (int i=n-1; i>=0; i--) {
		if (s[i] == 'I') {
			prv = i;
			continue;
		}
		if (s[i] == 'O') {
			if (prv == -1) {
				temp[i] = 1e8;
			} else {
				temp[i] = last[prv];
			}
		}
	}
	for (int i=0; i<n; i++) last[i] = temp[i];
	dq.clear();
	for (int i=n-1; i>=0; i--) {
		if (s[i] != 'O') continue;
		dq.push_front(i);
		if (dq.size() > k) dq.pop_back();
		if (dq.size() == k) {
			temp[i] = last[dq.back()];
		} else {
			temp[i] = 1e8;
		}
	}
	for (int i=0; i<n; i++) last[i] = temp[i];
	prv = -1;
	for (int i=n-1; i>=0; i--) {
		if (s[i] == 'O') {
			prv = i;
			continue;
		}
		if (s[i] == 'J') {
			if (prv == -1) {
				temp[i] = 1e8;
			} else {
				temp[i] = last[prv];
			}
		}
	}
	for (int i=0; i<n; i++) last[i] = temp[i];
	dq.clear();
	for (int i=n-1; i>=0; i--) {
		if (s[i] != 'J') continue;
		dq.push_front(i);
		if (dq.size() > k) dq.pop_back();
		if (dq.size() == k) {
			temp[i] = last[dq.back()];
		} else {
			temp[i] = 1e8;
		}
	}
	for (int i=0; i<n; i++) last[i] = temp[i];
	int o = 1e8;
	for (int i=0; i<n; i++) {
		if (s[i] != 'J') continue;
		if (last[i] == 1e8) continue;
		o = min(o, last[i]-i+1-3*k);
	}
	cout << (o == 1e8 ? -1 : o) << endl;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:20:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (dq.size() > k) dq.pop_back();
       ~~~~~~~~~~^~~
ho_t2.cpp:21:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (dq.size() == k) {
       ~~~~~~~~~~^~~~
ho_t2.cpp:47:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (dq.size() > k) dq.pop_back();
       ~~~~~~~~~~^~~
ho_t2.cpp:48:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (dq.size() == k) {
       ~~~~~~~~~~^~~~
ho_t2.cpp:74:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (dq.size() > k) dq.pop_back();
       ~~~~~~~~~~^~~
ho_t2.cpp:75:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (dq.size() == k) {
       ~~~~~~~~~~^~~~

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