QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#632009#9460. Diversity and Varianceucup-team2279#AC ✓189ms7716kbC++201.0kb2024-10-12 11:24:222024-10-14 17:20:10

Judging History

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

  • [2024-10-14 17:20:10]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:189ms
  • 内存:7716kb
  • [2024-10-14 17:20:06]
  • hack成功,自动添加数据
  • (/hack/993)
  • [2024-10-12 11:24:22]
  • 评测
  • 测评结果:100
  • 用时:195ms
  • 内存:7640kb
  • [2024-10-12 11:24:22]
  • 提交

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