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;
}

Download