oj.uz

Submission #555826

# Submission time Handle Problem Language Result Execution time Memory
555826 2022-05-01T15:51:13 Z Stickfish Diversity (CEOI21_diversity) C++17
0 / 100
 7000 ms 212 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long;

const int MAXN = 3e5 + 123;
int a[MAXN];

signed main() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    vector<int> cpr(n);
    for (int i = 0; i < n; ++i)
        cpr[i] = a[i];
    sort(cpr.begin(), cpr.end());
    cpr.resize(unique(cpr.begin(), cpr.end()) - cpr.begin());
    for (int i = 0; i < n; ++i)
        a[i] = lower_bound(cpr.begin(), cpr.end(), a[i]) - cpr.begin();
    for (int t = 0; t < q; ++t) {
        int l, r;
        cin >> l >> r;
        --l;
        int m = r - l;
        ll ans = 1ll * n * n * n;
        vector<int> permut(m);
        for (int i = 0; i < m; ++i)
            permut[i] = i;
        vector<int> permut_ = permut;
        do {
            vector<int> arr(m);
            for (int i = 0; i < m; ++i)
                arr[i] = a[l + permut[i]];
            ll curans = 0;
            for (int i = 0; i < m; ++i) {
                int msk = 0;
                for (int j = i; j < m; ++j) {
                    msk |= (1 << arr[j]);
                    curans += __builtin_popcount(msk);
                }
            }
            ans = min(ans, curans);
            next_permutation(permut.begin(), permut.end());
        } while (permut !=  permut_);
        cout << ans << '\n';
    }
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7013 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7035 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7035 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7035 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7013 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7013 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -