HAOI5000 - HAOI 5000

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long Long;
const int N = 1e6 + 5;
int c[N], n, k, nrst[N];

void enter() {
	scanf("%d%d",&n,&k);
	for(int i = 0; i < k; ++i) {
		int x; scanf("%d", &x);
		++c[x-1];
	}
}

void solve() {
	Long now = 0; int cnt = 0;
	for(int i = 0; i < n; ++i)
		now += (Long) c[i] * min(i, n-i); 
	for(int i = n/2; i >= 0; --i) cnt += c[i];
	Long nearest = now; int nNearest = 1; nrst[0] = 1;
	for(int l = 1, r = (n/2+1)%n; l < n; ++l, r = (r+1) % n) {
		now += k - 2*cnt + 2*c[l-1] - n % 2 * c[r];
		cnt += c[r] - c[l-1];
		if(now < nearest) nearest = now, nNearest = 0;
		if(now == nearest) nrst[nNearest++] = l + 1;
	}
	printf("%lld\n%d\n%d", nearest, nNearest, nrst[0]);
	for(int i = 1; i < nNearest; ++i) printf(" %d", nrst[i]);
	printf("\n");
}

int main() {
	enter();
	solve();
	return 0;
}

Download