Submission #291156

#	Time	Username	Problem	Language	Result	Execution time	Memory
291156		thiago4532	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	34 ms	8948 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 10;
char v[maxn];
int jsuf[maxn], osuf[maxn], isuf[maxn];
int jqtd[maxn], oqtd[maxn], iqtd[maxn];
int jp[maxn], op[maxn], ip[maxn];
vector<int> jv, ov, iv;

int main() {
	memset(jsuf, 0x3f, sizeof jsuf);
	memset(osuf, 0x3f, sizeof osuf);
	memset(isuf, 0x3f, sizeof isuf);

	int n_, k, n=0;
	cin >> n_ >> k;
	bool json = false;
	for (int i = 1; i <= n_; i++) {
		char x;
		cin >> x;
		if (!json && x != 'J') continue;
		json = true;
		v[++n] = x;
	}
	while (n > 0 && v[n] != 'I') n--;
	
	for (int i = 1; i <= n; i++) {
		if (v[i] == 'J') jv.push_back(i), jp[i] = jv.size() - 1;
		if (v[i] == 'O') ov.push_back(i), op[i] = ov.size() - 1;
		if (v[i] == 'I') iv.push_back(i), ip[i] = iv.size() - 1;
	}
	for (int i = n; i >= 1; i--) {
		jqtd[i] = jqtd[i+1];
		oqtd[i] = oqtd[i+1];
		iqtd[i] = iqtd[i+1];
		if (v[i] == 'J') jqtd[i] = jqtd[i+1] + 1;
		if (v[i] == 'O') oqtd[i] = oqtd[i+1] + 1;
		if (v[i] == 'I') iqtd[i] = iqtd[i+1] + 1;
	}
	if (jqtd[1] < k || oqtd[1] < k || iqtd[1] < k) {
		cout << "-1\n";
		return 0;
	}

	for (int i = 1; i <= n; i++) {
		if (v[i] != 'I') continue;
		int j = ip[i] + k - 1;
		if (j >= iv.size()) break;
		j = iv[j];

		isuf[i] = j - i - 1 - k + 2;
	}

	for (int i = n; i >= 1; i--) {
		isuf[i] = min(isuf[i], isuf[i+1] + 1);
	}

	for (int i = 1; i <= n; i++) {
		if (v[i] != 'O') continue;
		int j = op[i] + k - 1;
		if (j >= ov.size()) break;
		j = ov[j];
		
		osuf[i] = j - i - 1 - k + 2;
	}

	for (int i = n; i >= 1; i--) {
		int j = op[i] + k - 1;
		if (v[i] == 'O' && j < ov.size()) osuf[i] = min(osuf[i] + isuf[ov[j]+1], osuf[i+1] + 1);
		else osuf[i] = osuf[i+1] + 1;
	}

	for (int i = 1; i <= n; i++) {
		if (v[i] != 'J') continue;
		int j = jp[i] + k - 1;
		if (j >= jv.size()) break;
		j = jv[j];

		jsuf[i] = j - i - 1 - k + 2;
	}

	for (int i = n; i >= 1; i--) {
		int j = jp[i] + k - 1;
		if (v[i] == 'J' && j < jv.size()) jsuf[i] = min(jsuf[i] + osuf[jv[j]+1], jsuf[i+1]);
		else jsuf[i] = jsuf[i+1];
	}
	/*for (int i = 1; i<=n;i++)
		cout << isuf[i] <<  " \n"[i==n];

	for (int i = 1; i<=n;i++)
		cout << osuf[i] <<  " \n"[i==n];

	for (int i = 1; i<=n;i++)
		cout << jsuf[i] <<  " \n"[i==n];*/

	if (jsuf[1] >= 0x3f3f3f3f) cout << "-1\n";
	else cout << jsuf[1] << "\n";
	return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:49:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   if (j >= iv.size()) break;
      |       ~~^~~~~~~~~~~~
ho_t2.cpp:62:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   if (j >= ov.size()) break;
      |       ~~^~~~~~~~~~~~
ho_t2.cpp:70:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   if (v[i] == 'O' && j < ov.size()) osuf[i] = min(osuf[i] + isuf[ov[j]+1], osuf[i+1] + 1);
      |                      ~~^~~~~~~~~~~
ho_t2.cpp:77:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   if (j >= jv.size()) break;
      |       ~~^~~~~~~~~~~~
ho_t2.cpp:85:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   if (v[i] == 'J' && j < jv.size()) jsuf[i] = min(jsuf[i] + osuf[jv[j]+1], jsuf[i+1]);
      |                      ~~^~~~~~~~~~~

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