QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#631883#9460. Diversity and Varianceucup-team4863#AC ✓135ms5064kbC++141.7kb2024-10-12 10:47:262024-10-14 17:20:13

Judging History

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

  • [2024-10-14 17:20:13]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:135ms
  • 内存:5064kb
  • [2024-10-14 17:20:06]
  • hack成功,自动添加数据
  • (/hack/993)
  • [2024-10-12 10:47:27]
  • 评测
  • 测评结果:100
  • 用时:122ms
  • 内存:4908kb
  • [2024-10-12 10:47:26]
  • 提交

answer

// created:  2024-10-12 10:32:01
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<vector>
#define F(i,l,r) for(int i=l,i##_end=r;i<i##_end;++i)
#define I128 //||is_same<T,__int128_t>::value||is_same<T,__uint128_t>::value
using namespace std;
template<typename T>enable_if_t<is_integral<T>::value I128,void> readmain(T &x)
{
	bool neg=false;int c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')neg=true;
	for(x=0;isdigit(c);c=getchar())x=(T)(10*x+(c-'0'));
	if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}
typedef long long ll;
constexpr int N=1e5+5;
int n,m,b[N],a[N],c[N];
ll s1,s2,mv;
vector<int> seq(int k)
{
	vector<int> s;s.reserve(n-m);
	F(i,0,k)++c[a[i]];
	F(i,k+m,n)++c[a[i]];
	F(i,0,n)if(c[b[i]])--c[b[i]],s.emplace_back(i);
	return s;
}
void solve()
{
	read(n,m);
	F(i,0,n)b[i]=read(a[i]);
	if(!m)
	{
		F(i,0,n)printf("%d%c",i+1," \n"[i==n-1]);
		return;
	}
	if(m==n-1)
	{
		puts("1");
		return;
	}
	sort(a,a+n);
	s1=s2=0;
	F(i,m,n)s1+=a[i],s2+=(ll)a[i]*a[i];
	mv=(n-m)*s2-s1*s1;
	F(i,m,n)
	{
		s1-=a[i],s2-=(ll)a[i]*a[i];
		s1+=a[i-m],s2+=(ll)a[i-m]*a[i-m];
		mv=max(mv,(n-m)*s2-s1*s1);
	}
	vector<int> ans=vector<int>(1,n);
	bool fi=true;
	s1=s2=0;
	F(i,m,n)s1+=a[i],s2+=(ll)a[i]*a[i];
	if(mv==(n-m)*s2-s1*s1&&fi)ans=min(ans,seq(0));
	F(i,m,n)
	{
		s1-=a[i],s2-=(ll)a[i]*a[i];
		s1+=a[i-m],s2+=(ll)a[i-m]*a[i-m];
		fi=a[i]!=a[i-m];
		if(mv==(n-m)*s2-s1*s1&&fi)ans=min(ans,seq(i-m+1));
	}
	m=n-m;
	F(i,0,m)printf("%d%c",ans[i]+1," \n"[i==m-1]);
}
int main()
{
	int tt;read(tt);
	while(tt--)solve();
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 135ms
memory: 5064kb

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