Submission #1281771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281771		KickingKun	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	12 ms	3092 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define ld long double
#define bigint __int128
#define emb emplace_back
#define pb push_back
#define pii pair <int, int>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define Task ""

#define MASK(k) (1ull << k)
#define bitcnt(k) __builtin_popcount(k)
#define testBit(n, k) ((n >> k) & 1)
#define flipBit(n, k) (n ^ (1ll << k))
#define offBit(n, k) (n & ~MASK(k))
#define onBit(n, k) (n | (1ll << k))

template <class T> bool minimize(T &a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool maximize(T &a, T b) {if (a < b) {a = b; return true;} return false;}

const int N = 2e5 + 5, lim = 60, mod = 1e9 + 7;
const ll INF = 1e18;

int n, k, cnt[N][3];
string s;

int getJ(int l, int r) {
	return cnt[r][0] - cnt[l - 1][0];
}

int getO(int l, int r) {
	return cnt[r][1] - cnt[l - 1][1];
}

int getI(int l, int r) {
	return cnt[r][2] - cnt[l - 1][2];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	if (fopen(Task".inp", "r")) {
		freopen(Task".inp", "r", stdin);
		freopen(Task".out", "w", stdout);
	}

	cin >> n >> k;
	cin >> s; s = '#' + s;

	for (int i = 1; i <= n; i++) {
		cnt[i][0] = cnt[i - 1][0] + (s[i] == 'J');
		cnt[i][1] = cnt[i - 1][1] + (s[i] == 'O');
		cnt[i][2] = cnt[i - 1][2] + (s[i] == 'I');
	}

	int ans = 2e9;
	for (int i = 1; i <= n; i++) if (s[i] == 'J') {
		int l = i, r = n, pJ = -1;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (getJ(i, mid) >= k) r = (pJ = mid) - 1;
			else l = mid + 1;
		}
		if (pJ == -1) break;

		l = pJ + 1, r = n; int pO = -1;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (getO(pJ + 1, mid) >= k) r = (pO = mid) - 1;
			else l = mid + 1;
		}
		if (pO == -1) break;

		l = pO + 1, r = n; int pI = -1;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (getI(pO + 1, mid) >= k) r = (pI = mid) - 1;
			else l = mid + 1;
		}

		if (pI != -1) {
			minimize(ans, pI - i + 1 - 3 * k);
		}
	}
	cout << (ans <= n ? ans : -1);
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:48:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |                 freopen(Task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ho_t2.cpp:49:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |                 freopen(Task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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