HAOI5000 - HAOI 5000
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
int n,a[1000100];
vector <int> re;
int calc(int l,int r)
{
l=(l+n)%n;
r=(r+n)%n;
return a[r]-a[l-1]+(l>r?a[n-1]:0);
}
int main()
{
int k,x;
long long sumDist=0,best;
cin >> n >> k;
while (k--)
{
scanf("%d",&x);
a[--x]++;
sumDist+=min(x,n-x);
}
re.push_back(1);
best=sumDist;
for (int i=1;i<n;i++) a[i]+=a[i-1];
for (int i=1;i<n;i++)
{
sumDist+=calc(i-n/2,i-1)-calc(i,i+n/2-1);
if (sumDist==best) re.push_back(i+1);
if (sumDist<best)
{
best=sumDist;
re.assign(1,i+1);
}
}
cout << best << endl << re.size() << endl;
for (int i=0;i<re.size();i++) printf("%d ",re[i]);
return 0;
}