Submission #614257

#	Time	Username	Problem	Language	Result	Execution time	Memory
614257		Olympia	Nivelle (COCI20_nivelle)	C++17	110 / 110	907 ms	17028 KiB

nivelle

#include <bits/stdc++.h>
using namespace std;
struct SparseTable {
    vector<vector<int> > dp;
    int query (int l, int r) {
        int sz = log2(r - l + 1);
        return dp[l][sz] | dp[r - (1 << sz) + 1][sz];
    }
    SparseTable (string s) {
        int n = s.size();
        dp.resize(n);
        for (int i = 0; i < n; i++) {
            dp[i].resize(32);
            dp[i][0] = (1 << (s[i] - 'a'));
        }
        for (int j = 1; j <= 31; j++) {
            for (int i = 0; i < n; i++) {
                dp[i][j] = dp[i][j - 1] | dp[min((i + (1 << (j - 1))), n - 1)][j - 1];
            }
        }
    }
};
bool f (pair<int,int> p1, pair<int,int> p2) {
    return ((int64_t)p1.first * (int64_t)p2.second < (int64_t)p2.first * (int64_t)p1.second);
}
int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    SparseTable st(s);
    pair<int,int> p = make_pair(n, 1);
    pair<int,int> bounds;
    for (int i = 0; i < s.size(); i++) {
        int prev = i;
        for (int j = 1; j <= __builtin_popcount(st.query(i, (int)s.size() - 1)); j++) {
            int l = prev;
            int r = s.size() - 1;
            while (l != r) {
                int m = (l + r + 1)/2;
                if (__builtin_popcount(st.query(i, m)) <= j) {
                    l = m;
                } else {
                    r = m - 1;
                }
            }
            prev = l;
            pair<int,int> q = make_pair(j, l - i + 1);
            if (f(q, p)) {
                p = q;
                bounds = make_pair(i, l);
            }
        }
    }
    cout << bounds.first + 1 << " " << bounds.second + 1 << '\n';
}

Compilation message (stderr)

nivelle.cpp: In function 'int main()':
nivelle.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~

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