Submission #847399

#	Time	Username	Problem	Language	Result	Execution time	Memory
847399		AsandeiStefan	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	1 ms	344 KiB

ho_t2

#include <iostream>
#include <string>
#include <vector>

const char chars[] = { 'J', 'O', 'I' };

int n, k, start, end, nr3;
std::string s;
std::vector<int> pos[101];

bool is_possible() {
	for (int i = 0; i < 3; i++) {
		int c = 0;
		for (int j = 0; j < s.size(); j++) {
			if (s[j] == chars[i]) {
				c++;
				pos[i].push_back(j);
			}
			// if (c == k) break;
		}
		if (c < k)
			return false;
	}

	pos['J'] = pos[0];
	pos['O'] = pos[1];
	pos['I'] = pos[2];

	return true;
}

int first_max(int i) {
	int j = 0;
	while (pos[chars[i]][j] < start && j < pos[chars[i]].size()) j++;
	return pos[chars[i]][j];
}

int last_min(int i) {
	int j = pos[chars[i]].size()-1;
	while (pos[chars[i]][j] > end && j > 0) j--;
	return pos[chars[i]][j];
}


int main() {
	std::cin >> n >> k >> s;

	if (!is_possible()) {
done:
		std::cout << -1 << '\n';
		return 0;
	}

	for (start = 0; s[start] != 'J' && start < s.size(); start++);
	for (end = s.size()-1; s[end] != 'I' && end >= 0; end--);

	if (s.size() - (end - start) <= 0 || end < start)
		goto done;

	for (int i = 0; i < 3; i++) {
		int c = 0, j;
		for (j = first_max(i); j <= last_min(i); j++) {
			if (s[j] != chars[i])
				nr3++;
			else {
				c++;
				if (c == k) break;
			}
		}
		start = j;
	}

	std::cout << nr3 << '\n';

	return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'bool is_possible()':
ho_t2.cpp:14:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for (int j = 0; j < s.size(); j++) {
      |                   ~~^~~~~~~~~~
ho_t2.cpp: In function 'int first_max(int)':
ho_t2.cpp:34:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   34 |  while (pos[chars[i]][j] < start && j < pos[chars[i]].size()) j++;
      |             ~~~~~~~^
ho_t2.cpp:34:52: warning: array subscript has type 'char' [-Wchar-subscripts]
   34 |  while (pos[chars[i]][j] < start && j < pos[chars[i]].size()) j++;
      |                                             ~~~~~~~^
ho_t2.cpp:34:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  while (pos[chars[i]][j] < start && j < pos[chars[i]].size()) j++;
      |                                     ~~^~~~~~~~~~~~~~~~~~~~~~
ho_t2.cpp:35:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   35 |  return pos[chars[i]][j];
      |             ~~~~~~~^
ho_t2.cpp: In function 'int last_min(int)':
ho_t2.cpp:39:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |  int j = pos[chars[i]].size()-1;
      |              ~~~~~~~^
ho_t2.cpp:40:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   40 |  while (pos[chars[i]][j] > end && j > 0) j--;
      |             ~~~~~~~^
ho_t2.cpp:41:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   41 |  return pos[chars[i]][j];
      |             ~~~~~~~^
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:54:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for (start = 0; s[start] != 'J' && start < s.size(); start++);
      |                                     ~~~~~~^~~~~~~~~~

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