oj.uz

Submission #198408

# Submission time Handle Problem Language Result Execution time Memory
198408 2020-01-25T23:04:51 Z ZwariowanyMarcin Nivelle (COCI20_nivelle) C++14
110 / 110
 179 ms 10744 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define LL long long
#define ld long double
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, j, n) for(int i = j; i <= n; ++i)
#define boost cin.tie(0), ios_base::sync_with_stdio(0);


using namespace std;		

const int nax = 100100;

int n;
char s[nax];

int a[26];
int p[nax][26];

int gora, dol;
int l, r;

int main() {
	scanf ("%d", &n);
	scanf ("%s", s + 1);
	
	gora = 2;
	dol = 1;
	
	for (int i = 0; i < 26; ++i) a[i] = n + 1;
	for (int i = n; 1 <= i; --i) {
		for (int j = 0; j < 26; ++j)
			p[i][j] = a[j];
		a[s[i] - 'a'] = i;
	}
	
	for (int i = 1; i <= n; ++i) {
		int j = i;
		int mask = (1 << (s[i] - 'a'));
		while (j <= n) {
			int b = n + 1;
			for (int k = 0; k < 26; ++k)
				if (((mask >> k) & 1) == 0)
					b = min(b, p[j][k]);
			int dif = __builtin_popcount(mask);
			int dl = b - i;
			if (1LL * dif * dol < 1LL * gora * dl) {
				l = i;
				r = b - 1;
				gora = dif;
				dol = dl;
			}
			if (b <= n)
				mask |= (1 << (s[b] - 'a'));
			j = b;
		}
	}
	printf ("%d %d\n", l, r);		
			
	return 0;
}

Compilation message

nivelle.cpp: In function 'int main()':
nivelle.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &n);
  ~~~~~~^~~~~~~~~~
nivelle.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%s", s + 1);
  ~~~~~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 10616 KB Output is correct
2 Correct 19 ms 10616 KB Output is correct
3 Correct 20 ms 10616 KB Output is correct
4 Correct 18 ms 10616 KB Output is correct
5 Correct 19 ms 10616 KB Output is correct
6 Correct 19 ms 10616 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 10744 KB Output is correct
2 Correct 31 ms 10672 KB Output is correct
3 Correct 30 ms 10616 KB Output is correct
4 Correct 31 ms 10612 KB Output is correct
5 Correct 30 ms 10616 KB Output is correct
6 Correct 32 ms 10616 KB Output is correct

Subtask #5
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 10744 KB Output is correct
2 Correct 157 ms 10616 KB Output is correct
3 Correct 153 ms 10744 KB Output is correct
4 Correct 158 ms 10616 KB Output is correct
5 Correct 167 ms 10664 KB Output is correct
6 Correct 179 ms 10616 KB Output is correct