QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#633837#9460. Diversity and Varianceucup-team918#AC ✓252ms10516kbC++171.9kb2024-10-12 16:17:432024-10-14 17:20:20

Judging History

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

  • [2024-10-14 17:20:20]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:252ms
  • 内存:10516kb
  • [2024-10-14 17:20:06]
  • hack成功,自动添加数据
  • (/hack/993)
  • [2024-10-12 16:17:45]
  • 评测
  • 测评结果:100
  • 用时:278ms
  • 内存:10320kb
  • [2024-10-12 16:17:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;

bool have[N];
int cnt[N], a[N];
vector <int> val[N];
long long c[N];
priority_queue <int,vector<int>,greater<int> > add, del;

void work()
{
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);

	if(m==n-1)
	{
		printf("1\n");
		return;
	}

	for(int i=1;i<=n;i++)
		val[a[i]].push_back(i);

	sort(a+1,a+n+1);

	m=n-m;
	long long sum1=0, sum2=0;
	for(int i=n-m+1;i<=n;i++)
	{
		sum1 += a[i];
		sum2 += 1ll*a[i]*a[i];
	}

	for(int i=0;i<=m;i++)
	{
		c[i]=m*sum2-sum1*sum1;
		if(i!=m)
		{
			sum1 += a[i+1];
			sum1 -= a[n-m+1+i];
			sum2 += 1ll*a[i+1]*a[i+1];
			sum2 -= 1ll*a[n-m+1+i]*a[n-m+1+i];
		}
	}

	for(int i=1;i<=m;i++)
		cnt[a[i]]++;

	long long Max=-1, bestpos=-1;
	for(int i=m;i>=0;i--)
	{
		if(c[i]>Max)
		{
			Max=c[i], bestpos=i;
			while(add.size())
				add.pop();

			while(del.size())
				del.pop();
		}
		else if(c[i]==Max)
		{
			while(add.size() && del.size() && add.top()==del.top())
				add.pop(), del.pop();

			if(add.size() && del.size() && add.top()<del.top())
				bestpos=i;
		}

		if(i!=0)
		{
			cnt[a[i]]--;
			del.push(val[a[i]][cnt[a[i]]]);
			add.push(val[a[n-m+i]][cnt[a[n-m+i]]]);
			cnt[a[n-m+i]]++;
		}
	}

	while(add.size())
		add.pop();

	while(del.size())
		del.pop();

	for(int i=1;i<=n;i++)
		cnt[a[i]]=0;

	for(int i=1;i<=bestpos;i++)
		have[val[a[i]][cnt[a[i]]++]]=true;

	for(int i=n-m+bestpos+1;i<=n;i++)
		have[val[a[i]][cnt[a[i]]++]]=true;

	vector <int> ans;
	for(int i=1;i<=n;i++)
		if(have[i])
			ans.push_back(i);

	for(int i=0;i<(int)ans.size();i++)
	{
		if(i==(int)ans.size()-1)
			printf("%d\n",ans[i]);
		else
			printf("%d ",ans[i]);
	}

	for(int i=1;i<=n;i++)
		val[a[i]].clear(), cnt[a[i]]=0, have[i]=false;
}

int main()
{
	int T;
	cin >> T;
	while(T--)
		work();
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 6252kb

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: 252ms
memory: 10516kb

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