QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#633588 | #9460. Diversity and Variance | ucup-team5052# | AC ✓ | 253ms | 8712kb | C++17 | 2.3kb | 2024-10-12 15:47:41 | 2024-10-14 17:20:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 100005, V = 10005;
int n, a[N], m;
vector <int> adj[V];
int cnt[V], ans[N], cvs[N];
long long res = 0;
set <int> mdf[2];
inline void Read() {
cin >> n >> m;
for (int i = 1;i <= n;i++) {
cin >> a[i];
adj[a[i]].push_back(i);
}
}
inline void Solve() {
if (m == n - 1) {
cout << 1 << "\n";
return;
}
sort(a + 1, a + n + 1);
long long s1 = 0, s2 = 0;
for (int i = 1;i <= n;i++) ans[i] = cvs[i] = 0;
for (int i = m + 1;i <= n;i++) {
ans[adj[a[i]][cnt[a[i]]]] = cvs[adj[a[i]][cnt[a[i]]]] = 1;
cnt[a[i]]++;
s1 += a[i];
s2 += 1ll * a[i] * a[i];
}
res = (n - m) * s2 - s1 * s1;
mdf[0].clear();
mdf[1].clear();
for (int i = 1;i <= n - m;i++) {
cnt[a[i + m]]--;
int pos = adj[a[i + m]][cnt[a[i + m]]];
s1 -= a[i + m]; s2 -= 1ll * a[i + m] * a[i + m];
// cout << pos << " " << cvs[pos] << "\n";
if (cvs[pos] != ans[pos]) mdf[ans[pos]].erase(pos);
cvs[pos] = 0;
if (cvs[pos] != ans[pos]) mdf[ans[pos]].insert(pos);
pos = adj[a[i]][cnt[a[i]]];
cnt[a[i]]++;
s1 += a[i]; s2 += 1ll * a[i] * a[i];
// cout << pos << " " << cvs[pos] << "\n";
if (cvs[pos] != ans[pos]) mdf[ans[pos]].erase(pos);
cvs[pos] = 1;
if (cvs[pos] != ans[pos]) mdf[ans[pos]].insert(pos);
if ((n - m) * s2 - s1 * s1 > res || ((n - m) * s2 - s1 * s1 == res && !mdf[0].empty() && *(mdf[0].begin()) < *(mdf[1].begin()))) {
for (int x : mdf[0]) ans[x] = cvs[x];
for (int x : mdf[1]) ans[x] = cvs[x];
// cout << (n - m) * s2 - s1 * s1 << endl;
// for (int i = 1;i <= n;i++) cout << cvs[i] << ' ';
// cout << endl;
mdf[0].clear();
mdf[1].clear();
res = (n - m) * s2 - s1 * s1;
}
}
int cnt1 = 0;
for (int i = 1;i <= n;i++) {
if (ans[i]) {
cnt1++;
cout << i << " \n"[cnt1 == n - m];
}
}
}
inline void Clear() {
/*
int n, a[N];
vector <int> adj[V];
int cnt[V], ans[N], cvs[N];
long long res = 0;
set <int> mdf[2];*/
for (int i = 1;i <= n;i++) {
adj[a[i]].clear();
cnt[a[i]] = 0;
ans[i] = cvs[i] = 0;
}
res = 0;
mdf[0].clear();
mdf[1].clear();
}
int main() {
std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
Read();
Solve();
Clear();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3956kb
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: 253ms
memory: 8712kb
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