oj.uz

Submission #198407

# Submission time Handle Problem Language Result Execution time Memory
198407 2020-01-25T23:01:37 Z ZwariowanyMarcin Nivelle (COCI20_nivelle) C++14
103 / 110
 189 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 - j;
			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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

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 6 ms 504 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 10616 KB Output is correct
2 Correct 19 ms 10628 KB Output is correct
3 Correct 19 ms 10516 KB Output is correct
4 Correct 19 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 10616 KB Output is correct
2 Correct 32 ms 10632 KB Output is correct
3 Correct 31 ms 10616 KB Output is correct
4 Correct 32 ms 10616 KB Output is correct
5 Correct 32 ms 10616 KB Output is correct
6 Correct 33 ms 10616 KB Output is correct

Subtask #5
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 10636 KB Output is correct
2 Correct 172 ms 10636 KB Output is correct
3 Correct 169 ms 10616 KB Output is correct
4 Correct 174 ms 10632 KB Output is correct
5 Correct 178 ms 10604 KB Output is correct
6 Correct 189 ms 10744 KB Output is correct