Submission #206149

#	Time	Username	Problem	Language	Result	Execution time	Memory
206149		luciocf	Grudanje (COCI19_grudanje)	C++14	70 / 70	343 ms	13944 KiB

grudanje

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int maxn = 1e5+10;

int n, q;
string a;

int p[maxn];

int pref[28][maxn];

bool mark[maxn];

pii range[maxn];

bool ok(int t)
{
	memset(mark, 0, sizeof mark);

	for (int i = 1; i <= t; i++)
		mark[p[i]] = 1;

	for (int c = 0; c < 26; c++)
	{
		for (int i = 1; i <= n; i++)
		{
			if (mark[i] || a[i-1] != (char)(c+'a')) pref[c][i] = pref[c][i-1];
			else pref[c][i] = pref[c][i-1]+1;
		}
	}

	for (int i = 1; i <= q; i++)
	{
		bool ok = 1;

		for (int c = 0; c < 26; c++)
			if (pref[c][range[i].second]-pref[c][range[i].first-1] > 1)
				ok = 0;

		if (!ok) return false;
	}

	return true;
}

int busca(void)
{
	int ini = 0, fim = n, ans = n;

	while (ini <= fim)
	{
		int mid = (ini+fim)>>1;

		if (ok(mid)) ans = mid, fim = mid-1;
		else ini = mid+1;
	}

	return ans;
}

int main(void)
{
	cin >> a;
	n = a.size();

	scanf("%d", &q);

	for (int i = 1; i <= q; i++)
		scanf("%d %d", &range[i].first, &range[i].second);

	for (int i = 1; i <= n; i++)
		scanf("%d", &p[i]);

	printf("%d\n", busca());
}

Compilation message (stderr)

grudanje.cpp: In function 'int main()':
grudanje.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
grudanje.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &range[i].first, &range[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
grudanje.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p[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