QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#698198#9460. Diversity and VarianceCryingAC ✓245ms8556kbC++141.9kb2024-11-01 18:05:312024-11-01 18:05:34

Judging History

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

  • [2024-11-01 18:05:34]
  • 评测
  • 测评结果:AC
  • 用时:245ms
  • 内存:8556kb
  • [2024-11-01 18:05:31]
  • 提交

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