Submission #1102332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102332		MinhKien	Nivelle (COCI20_nivelle)	C++17	24 / 110	1068 ms	12372 KiB

nivelle

#include <iostream>
#include <string>

using namespace std;

const int N = 1e5 + 10;
int n, c[N][30];
string s;

int diff(int l, int r) {
    int cnt = 0;
    for (int i = 0; i < 26; ++i) {
        if (c[r][i] - c[l - 1][i] > 0) ++cnt;
    }
    return cnt;
}

int Find(int L, int d) {
    int l = L, r = n, ans = -1;

    while (l <= r) {
        int m = (l + r) >> 1;

        int p = diff(L, m);
        if (p <= d) {
            if (p == d) ans = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    return ans;
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    cin >> n >> s;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 26; ++j) c[i][j] = c[i - 1][j];
        ++c[i][s[i - 1] - 'a'];
    }

    long double Min = 1e17;
    int l, r;

    for (int d = 1; d <= 26; ++d) {
        for (int i = 1; i <= n; ++i) {
            int k = Find(i, d);

            if (k == -1) continue;

            long double p = (long double)(d) / (long double)(k - i + 1);
            if (p < Min) {
                Min = p;
                l = i;
                r = k;
            }
        }
    }

    cout << l << " " << r << "\n";

    return 0;
}

Compilation message (stderr)

nivelle.cpp: In function 'int main()':
nivelle.cpp:65:30: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |     cout << l << " " << r << "\n";
      |                              ^~~~
nivelle.cpp:65:18: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |     cout << l << " " << r << "\n";
      |                  ^~~

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