Submission #478590

#	Time	Username	Problem	Language	Result	Execution time	Memory
478590		Neos	Nivelle (COCI20_nivelle)	C++14	24 / 110	1092 ms	10696 KiB

nivelle

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vii> vvii;
 
#define task "test"
#define fastIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define forw(i, l, r) for( ll i = (l) ; i < (r) ; i++ )
#define forb(i, r, l) for( ll i = (r) ; i >= (l) ; i-- )
#define sz(x) (int)x.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define numBit(x) __builtin_popcount(x)
#define lb lower_bound
#define ub upper_bound
#define ar array
#define endl '\n'
 
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
 
const int N = 2e5 + 7;
const ll inf = 0x3f3f3f3f;

int n, cnt[26], p[N][26];
string s;

int calc(int l, int r) {
  int cnt = 0;
  forw(i, 0, 26) cnt += (p[r][i] - p[l - 1][i] > 0);
  return cnt;
}

int main() {
  fastIO;

  cin >> n >> s;
  s = ' ' + s;
  forw(i, 1, sz(s)) forw(j, 0, 26)
    p[i][j] += p[i - 1][j] + (s[i] - 'a' == j);  

  ld ans = 26;
  int L = -1, R = -1;
  forw(k, 1, 27) forw(i, 1, n + 1) {
    int l = i, r = n, res = -1;
    while (l <= r) {
      int mid = l + r >> 1;
      // if (k == 2 && i == 3) cerr << mid << endl;
      if (calc(i, mid) <= k) res = mid, l = mid + 1;
      else r = mid - 1;
    }

    // if (k == 2 && i == 4) cerr << ans << ' ' << k << ' ' << res << ' ' << k * 1.0 / (res - i + 1) << endl;
    if (ans != -1 && calc(i, res) == k && k * 1.0 / (res - i + 1) < ans){
      ans = k * 1.0 / (res - i + 1);
      L = i, R = res;
    }
    // if (ans == 0.5) {
    //   cerr << "lmao" << ans << endl;
    //   cerr << k << ' ' << res - i + 1 << endl;
    //   return 0;
    // }
  }
  cout << L << ' ' << R << endl;
} 

Compilation message (stderr)

nivelle.cpp: In function 'int main()':
nivelle.cpp:58:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |       int mid = l + r >> 1;
      |                 ~~^~~

• Subtask 1: 7 / 7
• Subtask 2: 17 / 17
• Subtask 3: 0 / 13
• Subtask 4: 0 / 25
• Subtask 5: 0 / 48