QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#698198 | #9460. Diversity and Variance | Crying | AC ✓ | 245ms | 8556kb | C++14 | 1.9kb | 2024-11-01 18:05:31 | 2024-11-01 18:05:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef array<int,2> pr;
const ll N = 1e5+10,INF = 4e18;
template<typename T>void tomin(T& x,T y){x = min(x,y);}
template<typename T>void tomax(T& x,T y){x = max(x,y);}
//
int T,n,m; ll pre[N],pre2[N],suf[N],suf2[N];
pr a[N]; ll ans; vector<int> res;
ll F(int i){
ll S = pre[i] + suf[n-(m-i)+1];
ll S2 = pre2[i] + suf2[n-(m-i)+1];
return m*S2 - S*S;
}
int cmp(vector<int>& x,vector<int>& y){
for(int i=0;i<m;i++)if(x[i]!=y[i])return x[i] > y[i];
return 0;
}
void solve(){
cin>>n>>m; m = n-m;
for(int i=1;i<=n;i++)cin>>a[i][0],a[i][1] = i;
if(m==1){
cout<<"1\n";
return;
}
sort(a+1,a+1+n);
pre[0] = suf[n+1] = 0; for(int i=1;i<=n;i++)pre[i] = pre[i-1] + a[i][0]; for(int i=n;i>=1;i--)suf[i] = suf[i+1] + a[i][0];
pre2[0] = suf2[n+1] = 0; for(int i=1;i<=n;i++)pre2[i] = pre2[i-1] + a[i][0]*a[i][0]; for(int i=n;i>=1;i--)suf2[i] = suf2[i+1] + a[i][0] * a[i][0];
ans = -INF; res.clear();
for(int i=m;i>=0;i--)if(F(i) > ans)ans = F(i);
for(int i=m;i>=0;i--){
int L = i,R = n-(m-i)+1;
if(L && R<=n && a[L][0] == a[R][0])continue;
if(F(i) == ans){
vector<int> now;
for(int j=1;j<=L;j++)now.push_back(a[j][1]);
int k = R,p = R;
while(k<n && a[k+1][0] == a[k][0])k++;
while(p != n+1 && p-1>L && a[p-1][0] == a[p][0])p--;
for(int j=k+1;j<=n;j++)now.push_back(a[j][1]);
int cnt = k-R+1; if(i==m)cnt = 0;
for(int j=0;j<cnt;j++)now.push_back(a[p+j][1]);
sort(now.begin(),now.end());
if(res.empty() || cmp(res,now))res = now;
}
}
for(int i=0;i<m-1;i++)cout<<res[i]<<" "; cout<<res[m-1]<<"\n";
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
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: 5636kb
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: 245ms
memory: 8556kb
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