Submission #1187513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187513		lopkus	Nivelle (COCI20_nivelle)	C++20	110 / 110	24 ms	584 KiB

nivelle

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

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(x) cerr << "[" << #x << " = " << (x) << "]" << endl

#define left    __left
#define right   __right
#define prev    __prev
#define fi      first
#define se      second

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

int lenS;
string s;

int cnt[27];

namespace subtask2 {
    bool check() {
        return (lenS <= 2000);
    }

    void solve() {
        s = '*' + s;

        pair <int, int> result = {1, 1};
        pair <int, int> ans = {1, 1}; // num diff / num element;
        FOR(i, 1, lenS) {
            memset(cnt, 0, sizeof(cnt));
            int diff = 0;
            FOR(j, i, lenS) {
                cnt[s[j] - 'a']++;
                if (cnt[s[j] - 'a'] == 1) ++diff;

                if (ans.fi * (j - i + 1) > diff * ans.se) {
                    ans = make_pair(diff, j - i + 1);
                    result = make_pair(i, j);
                }
            }
        }

        cout << result.fi << " " << result.se;
    }
};

namespace subtask5 {
    void solve() {
        s = '*' + s;
        // with each numDiff, find maxLength;

        pair <int, int> result = {1, 1};
        pair <int, int> ans = {1, 1}; // num diff / num element;
        FOR(numDiff, 1, 26) {
            memset(cnt, 0, sizeof(cnt));
            int diff = 0;

            int l = 1, r = 1, len = 0;
            pair <int, int> cur_pos = {-1, -1};
            while (l <= lenS && r <= lenS) {
                cnt[s[r] - 'a']++;
                if (cnt[s[r] - 'a'] == 1) ++diff;
                while (diff > numDiff) {
                    cnt[s[l] - 'a']--;
                    if (cnt[s[l] - 'a'] == 0) --diff;
                    ++l;
                }

                if (diff == numDiff) {
                    if (maximize(len, r - l + 1)) cur_pos = make_pair(l, r);
                }

                ++r;
            }

            if (len == 0) break;

            if (ans.fi * len > numDiff * ans.se) {
                ans = make_pair(numDiff, len);
                result = cur_pos;
            }
        }

        cout << result.fi << " " << result.se;
    }
};

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    cin >> lenS;
    cin >> s;

//    if (subtask2 :: check()) return subtask2 :: solve(), 0;
    subtask5 :: solve();

    return 0;
}

/* Discipline - Calm */

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