QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#631883 | #9460. Diversity and Variance | ucup-team4863# | AC ✓ | 135ms | 5064kb | C++14 | 1.7kb | 2024-10-12 10:47:26 | 2024-10-14 17:20:13 |
Judging History
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