QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#658051 | #9460. Diversity and Variance | ucup-team004 | AC ✓ | 242ms | 4772kb | C++23 | 2.5kb | 2024-10-19 16:03:41 | 2024-10-19 16:03:42 |
Judging History
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