QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#658051#9460. Diversity and Varianceucup-team004AC ✓242ms4772kbC++232.5kb2024-10-19 16:03:412024-10-19 16:03:42

Judging History

你现在查看的是最新测评结果

  • [2024-10-19 16:03:42]
  • 评测
  • 测评结果:AC
  • 用时:242ms
  • 内存:4772kb
  • [2024-10-19 16:03:41]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

void solve() {
    int n, m;
    std::cin >> n >> m;
    
    m = n - m;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    std::vector<int> ord(n);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(),
        [&](int i, int j) {
            if (a[i] != a[j]) {
                return a[i] < a[j];
            }
            return i < j;
        });
    
    if (m == 1) {
        std::cout << 1 << "\n";
        return;
    }
    
    i64 s1 = 0, s2 = 0;
    for (int i = n - m; i < n; i++) {
        s1 += a[ord[i]];
        s2 += a[ord[i]] * a[ord[i]];
    }
    i64 ans = s2 * m - s1 * s1;
     
    for (int i = 0; i < m; i++) {
        s1 += a[ord[i]];
        s2 += a[ord[i]] * a[ord[i]];
        s1 -= a[ord[i + n - m]];
        s2 -= a[ord[i + n - m]] * a[ord[i + n - m]];
        ans = std::max(ans, s2 * m - s1 * s1);
    }
    
    std::vector<int> p;
    
    s1 = 0, s2 = 0;
    for (int i = n - m; i < n; i++) {
        s1 += a[ord[i]];
        s2 += a[ord[i]] * a[ord[i]];
    }
    
    auto check = [&](int l) {
        std::vector<int> q;
        for (int i = 0; i < l; i++) {
            q.push_back(ord[i]);
        }
        int x = l + n - m;
        int y = x;
        while (y < n && a[ord[x]] == a[ord[y]]) {
            y++;
        }
        for (int i = y; i < n; i++) {
            q.push_back(ord[i]);
        }
        while (x > l && a[ord[x - 1]] == a[ord[y - 1]]) {
            x--;
            y--;
        }
        for (int i = x; i < y; i++) {
            q.push_back(ord[i]);
        }
        std::sort(q.begin(), q.end());
        if (p.empty() || p > q) {
            p = q;
        }
    };
    
    for (int i = 0; i <= m; i++) {
        if (ans == s2 * m - s1 * s1 && (i == 0 || a[ord[i - 1]] != a[ord[i - 1 + n - m]])) {
            check(i);
        }
        if (i < m) {
            s1 += a[ord[i]];
            s2 += a[ord[i]] * a[ord[i]];
            s1 -= a[ord[i + n - m]];
            s2 -= a[ord[i + n - m]] * a[ord[i + n - m]];
        }
    }
    for (int i = 0; i < m; i++) {
        std::cout << p[i] + 1 << " \n"[i == m - 1];
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3524kb

input:

9
3 2
34 35 36
4 2
20 35 41 74
5 2
40 30 50 20 10
5 2
50 40 30 20 10
5 2
10 20 30 40 50
5 3
30 40 20 10 50
5 4
10 20 30 40 50
5 1
30 50 40 20 10
5 0
30 50 40 20 10

output:

1
1 4
1 3 5
1 2 5
1 2 5
4 5
1
2 3 4 5
1 2 3 4 5

result:

ok 9 lines

Test #2:

score: 0
Accepted
time: 242ms
memory: 4772kb

input:

30713
38 30
2 3 8 2 0 0 4 4 5 4 8 1 2 1 3 2 0 9 5 6 6 4 8 8 1 4 6 2 3 2 0 9 2 5 8 2 3 2
8 1
5222 2247 8017 1046 1922 9545 1396 2722
8 4
99 99 99 9999 999 9 1 9999
99 98
1 3 3 3 8 8 9 7 3 8 0 6 5 6 1 5 3 7 8 6 4 5 4 5 7 9 6 7 0 5 0 0 9 0 9 0 1 1 3 1 4 5 9 2 8 8 1 2 8 0 1 2 3 6 3 9 1 6 2 7 8 0 5 3 8 7...

output:

3 5 6 11 17 18 31 32
2 3 4 5 6 7 8
4 6 7 8
1
1 2 4 5 7 8
1 5
1 2 3
1 2 3 4 6 7 8
1
11 14 19 22 28 31 35 37 38 39 45 46 47 51 54 59 64 68 74 77 82 85 86 91 95
1
1 3
1 3 4 5 6 7 8 10 13 14 17 19 23 24 25 26 27 33 39 40
1
1 2 3 4 5 6 7
1 2 3 5 6 7 8 9 10 11 12 13 14 15 16 17 19 20 21 23 24 25 26 27 28 ...

result:

ok 30713 lines

Extra Test:

score: 0
Extra Test Passed