Submission #198408

#	Time	Username	Problem	Language	Result	Execution time	Memory
198408		ZwariowanyMarcin	Nivelle (COCI20_nivelle)	C++14	110 / 110	179 ms	10744 KiB

nivelle

#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 (stderr)

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 / 7
• Subtask 2: 17 / 17
• Subtask 3: 13 / 13
• Subtask 4: 25 / 25
• Subtask 5: 48 / 48