Submission #222370

#	Time	Username	Problem	Language	Result	Execution time	Memory
222370		shenxy	Grudanje (COCI19_grudanje)	C++11	70 / 70	230 ms	12028 KiB

grudanje

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
typedef pair<int, int> ii;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string S;
	cin >> S;
	int Q;
	cin >> Q;
	int a[Q], b[Q], p[S.size()], l, u, m, psum[S.size() + 1][26];
	for (int i = 0; i < Q; ++i) cin >> a[i] >> b[i];
	for (int i = 0; i < S.size(); ++i) cin >> p[i];
	l = 0, u = S.size() - 1;
	while (l != u) {
		m = (l + u) / 2;
		memset(psum, 0, sizeof psum);
		for (int i = 1; i <= S.size(); ++i) {
			if (p[i - 1] > m) psum[i][S[i - 1] - 'a'] = 1;
		}
		for (int i = 1; i <= S.size(); ++i) {
			for (int j = 0; j < 26; ++j) psum[i][j] += psum[i - 1][j];
		}
		bool perfect = true;
		for (int i = 0; i < Q; ++i) {
			for (int j = 0; j < 26; ++j) {
				if (psum[b[i]][j] - psum[a[i] - 1][j] > 1) perfect = false;
			}
		}
		if (perfect) u = m;
		else l = m + 1;
	}
	cout << l;
	return 0;
}

Compilation message (stderr)

grudanje.cpp: In function 'int main()':
grudanje.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); ++i) cin >> p[i];
                  ~~^~~~~~~~~~
grudanje.cpp:22:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i <= S.size(); ++i) {
                   ~~^~~~~~~~~~~
grudanje.cpp:25:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i <= S.size(); ++i) {
                   ~~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7