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