QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#632009 | #9460. Diversity and Variance | ucup-team2279# | AC ✓ | 189ms | 7716kb | C++20 | 1.0kb | 2024-10-12 11:24:22 | 2024-10-14 17:20:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+5;
int n,m,a[N],l[N],r[N];
vector<int> p[N];
void solve(){
cin>>n>>m;
m=n-m;
for(int i=1;i<=n;i++) cin>>a[i],p[a[i]].clear();
for(int i=1;i<=n;i++) p[a[i]].push_back(i);
sort(a+1,a+n+1);
for(int i=1,t=0;i<=n;i++) l[i]=t,t=(a[i]==a[i+1]?t+1:0);
for(int i=n,t=0;i;i--) r[i]=t,t=(a[i]==a[i-1]?t+1:0);
ll s=0,s2=0;
for(int i=1;i<=m;i++) s+=a[i],s2+=a[i]*a[i];
ll mx=s2*m-s*s;
int h=m+1;
for(int i=0;i<m;i++){
s+=a[n-i]-a[m-i];
s2+=a[n-i]*a[n-i]-a[m-i]*a[m-i];
if(a[n-i]==a[m-i]) continue;
ll v=s2*m-s*s;
if(v>mx||(v==mx&&p[a[m-i]][l[m-i]]>p[a[n-i]][r[n-i]]))
mx=v,h=m-i;
}
vector<int> ans;
for(int i=1;i<h;i++) ans.push_back(p[a[i]][l[i]]);
for(int i=h+n-m;i<=n;i++) ans.push_back(p[a[i]][r[i]]);
sort(begin(ans),end(ans));
if(m==1) cout<<"1\n";
else for(int i=0;i<m;i++) cout<<ans[i]<<" \n"[i==m-1];
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int t;
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: 1ms
memory: 5644kb
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: 189ms
memory: 7716kb
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