QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#633837 | #9460. Diversity and Variance | ucup-team918# | AC ✓ | 252ms | 10516kb | C++17 | 1.9kb | 2024-10-12 16:17:43 | 2024-10-14 17:20:20 |
Judging History
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