Submission #1281057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281057		paronmanukyan	Nivelle (COCI20_nivelle)	C++20	110 / 110	60 ms	14232 KiB

nivelle

#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define sort_uniq(x) sort(all(x)), uniq(x);
#define no_el(x, y) x.find(y) == x.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vct vector
#define vct2dll vct<vct<ll>>
#define vct2dint vct<vct<int>>
#define vct2dchar vct<vct<char>>
#define vct2dbool vct<vct<bool>>
#define vct3dll vct<vct<vct<ll>>>
#define vct3dint vct<vct<vct<int>>>
#define vct3dchar vct<vct<vct<char>>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define FASTIO                                                                 \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(nullptr);                                                            \
  cout.tie(nullptr);
#define INF INT32_MAX
#define blt __builtin_popcount
#define clr(x) x.clear()
#define ff first
#define ss second
#define popf pop_front
#define popb pop_back
#define sz(x) int(x.size())

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int main()
{
    FASTIO
    int n; cin >> n;
    string s; cin >> s;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        a[i] = s[i - 1] - 'a';

    vct2dint nxt(n + 2, vector<int>(26));
    for (int i = 0; i < 26; ++i) nxt[n + 1][i] = n + 1;
    for (int i = n; i >= 1; --i) {
        for (int j = 0; j < 26; ++j) {
            nxt[i][j] = (a[i] == j ? i : nxt[i + 1][j]);
        }
    }

    ld ans = 1.0;
    int l = 1, r = 1;
    for (int i = 1; i <= n; ++i) {
        vector<int> cur;
        for (int j = 0; j < 26; ++j)
            cur.pb(nxt[i][j]);
        cur.pb(n + 1);
        sort(all(cur));
        while (sz(cur) >= 2 && cur[sz(cur) - 2] == n + 1)
            cur.popb();

        for (int j = 1; j < sz(cur); ++j) {
            ld cr = (ld)(cur[j] - i) / j;
            if (cr > ans) {
                ans = cr;
                l = i;
                r = cur[j] - 1;
            }
        }
    }

    cout << l << ' ' << r;
}

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