Submission #198407

#TimeUsernameProblemLanguageResultExecution timeMemory
198407ZwariowanyMarcinNivelle (COCI20_nivelle)C++14
103 / 110
189 ms10744 KiB
#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 (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);
  ~~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...