제출 #614253

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
614253		Olympia	Nivelle (COCI20_nivelle)	C++17	0 / 110	964 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++) {
        for (int j = 1; j <= __builtin_popcount(st.query(i, (int)s.size() - 1)); j++) {
            int l = i;
            int r = s.size() - 1;
            while (l != r) {
                int m = (l + r)/2;
                if (__builtin_popcount(st.query(i, m)) >= j) {
                    r = m;
                } else {
                    l = m + 1;
                }
            }
            pair<int,int> q = make_pair(j, l - i + 1);
            if (f(q, p)) {
                p = q;
                bounds = make_pair(i, l);
            }
            //cout << l << ' ';
        }
        //cout << '\n';
    }
    //cout << bounds.first << " " << bounds.second << '\n';
    cout << p.first + 1 << " " << p.second + 1 << '\n';
}

컴파일 시 표준 에러 (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: 0 / 7
• Subtask 2: 0 / 17
• Subtask 3: 0 / 13
• Subtask 4: 0 / 25
• Subtask 5: 0 / 48