oj.uz

Submission #206165

# Submission time Handle Problem Language Result Execution time Memory
206165 2020-03-02T15:02:55 Z luciocf Nivelle (COCI20_nivelle) C++14
110 / 110
 103 ms 1268 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int n;
char a[maxn];

vector<int> pos[27];

bool good(int a, int b, int c, int d)
{
	return c*b < a*d;
}

int main(void)
{
	scanf("%d", &n);

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

	for (int i = n; i >= 1; i--)
		pos[(int)(a[i]-'a')].push_back(i);

	int opt_a = 1, opt_b = 1;
	int opt_l = 1, opt_r = 1;

	for (int i = 1; i <= n; i++)
	{
		vector<int> p;

		for (int j = 0; j < 26; j++)
			if (pos[j].size() > 0)
				p.push_back(pos[j].back());

		sort(p.begin(), p.end());
		p.push_back(n+1);

		for (int j = 1; j < p.size(); j++)
		{
			if (good(opt_a, opt_b, j, p[j]-i))
			{
				opt_a = j, opt_b = p[j]-i;
				opt_l = i, opt_r = p[j]-1;
			}
		}

		pos[(int)(a[i]-'a')].pop_back();
	}

	printf("%d %d\n", opt_l, opt_r);
}

Compilation message

nivelle.cpp: In function 'int main()':
nivelle.cpp:41:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < p.size(); j++)
                   ~~^~~~~~~~~~
nivelle.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
nivelle.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &a[i]);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 248 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 128 KB Output is correct
6 Correct 5 ms 256 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 244 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 7 ms 376 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1140 KB Output is correct
2 Correct 27 ms 1180 KB Output is correct
3 Correct 28 ms 1208 KB Output is correct
4 Correct 27 ms 1268 KB Output is correct
5 Correct 27 ms 1140 KB Output is correct
6 Correct 28 ms 1128 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1016 KB Output is correct
2 Correct 39 ms 964 KB Output is correct
3 Correct 34 ms 968 KB Output is correct
4 Correct 34 ms 1144 KB Output is correct
5 Correct 34 ms 1144 KB Output is correct
6 Correct 34 ms 1144 KB Output is correct

Subtask #5
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 1016 KB Output is correct
2 Correct 92 ms 1016 KB Output is correct
3 Correct 86 ms 1016 KB Output is correct
4 Correct 93 ms 1144 KB Output is correct
5 Correct 97 ms 1016 KB Output is correct
6 Correct 103 ms 1044 KB Output is correct