Submission #389560

---

Source Code Expand

#include <cstdio>
#include <bitset>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;

int N, K, A, B;
int Xi[606];
bitset<180001> bs[606];
int d1[180001], d2[180001];

bitset<180001> memo[31][301];
const int W = 20;

vector<int> restore(int sum)
{
	vector<int> ret;
	int loc = N, rem = K;
	while (loc) {
		int step = loc % W;
		if (step == 0) step = W;
		int rt = loc - step;
		for (int i = 0; i < (1 << step); ++i) {
			int tot = 0, cnt = __builtin_popcount(i);
			for (int j = 0; j < step; ++j) if (i & (1 << j)) tot += Xi[rt + j];
			if (rem >= cnt && sum >= tot && rem - cnt <= rt && memo[rt / W][rem - cnt][sum - tot]) {
				rem -= cnt;
				sum -= tot;
				for (int j = 0; j < step; ++j) if (i & (1 << j)) {
					ret.push_back(rt + j);
				}

				goto nex;
			}
		}
		fprintf(stderr, "><");
		break;
	nex:
		loc -= step;
	}
	sort(ret.begin(), ret.end());
	return ret;
}

int main()
{
	scanf("%d%d%d%d", &N, &K, &A, &B);
	for (int i = 0; i < N; ++i) scanf("%d", Xi + i);
	bs[0].set(0);

	if (K <= N / 2) {
		for (int i = 0; i <= N; ++i) {
			if (i % W == 0) {
				for (int j = 0; j <= K; ++j) memo[i / W][j] = bs[j];
			}
			if (i == N) break;
			for (int j = K; j >= 1; --j) bs[j] |= bs[j - 1] << Xi[i];
		}

		for (int i = 0; i <= 180000; ++i) d1[i] = d2[i] = 10000000;
		for (int i = 0; i <= 180000; ++i) if ((int)bs[K][i]) d1[i] = d2[i] = 0;

		for (int i = 1; i <= 180000; ++i) d1[i] = min(d1[i], d1[i - 1] + 1);
		for (int i = 179999; i >= 0; --i) d2[i] = min(d2[i], d2[i + 1] + 1);

		pair<int, int> ret = make_pair(-114514, 0);
		for (int i = A; i <= B; ++i) ret = max(ret, make_pair(min(d1[i], d2[i]), -i));
		printf("%d\n", -ret.second);

		int finder;
		int s = ret.second * -1;
		if (d1[s] > d2[s]) finder = s + d2[s];
		else finder = s - d1[s];
		vector<int> res = restore(finder);
		for (int i = 0; i < res.size(); ++i) {
			if (i > 0) printf(" ");
			printf("%d", res[i] + 1);
		}
		puts("");
	} else {
		K = N - K;
		int total = 0;
		for (int i = 0; i < N; ++i) total += Xi[i];

		for (int i = 0; i <= N; ++i) {
			if (i % W == 0) {
				for (int j = 0; j <= K; ++j) memo[i / W][j] = bs[j];
			}
			if (i == N) break;
			for (int j = K; j >= 1; --j) bs[j] |= bs[j - 1] << Xi[i];
		}

		for (int i = 0; i <= 180000; ++i) d1[i] = d2[i] = 10000000;
		for (int i = 0; i <= 180000; ++i) if ((int)bs[K][i] && 0 <= total - i && total - i <= 180000) d1[total - i] = d2[total - i] = 0;

		for (int i = 1; i <= 180000; ++i) d1[i] = min(d1[i], d1[i - 1] + 1);
		for (int i = 179999; i >= 0; --i) d2[i] = min(d2[i], d2[i + 1] + 1);

		pair<int, int> ret = make_pair(-114514, 0);
		for (int i = A; i <= B; ++i) ret = max(ret, make_pair(min(d1[i], d2[i]), -i));
		printf("%d\n", -ret.second);

		int finder;
		int s = ret.second * -1;
		if (d1[s] > d2[s]) finder = s + d2[s];
		else finder = s - d1[s];
		finder = total - finder;
		vector<int> res = restore(finder);

		bool a[6000];
		for (int i = 0; i < N; ++i) a[i] = false;
		for (int i = 0; i < res.size(); ++i) a[res[i]] = true;

		bool u = false;
		for (int i = 0; i < N; ++i) if (!a[i]) {
			if (u) printf(" ");
			u = true;
			printf("%d", i + 1);
		}
		puts("");
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:48:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &N, &K, &A, &B);
                                   ^
./Main.cpp:49:49: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < N; ++i) scanf("%d", Xi + i);
                                                 ^

Judge Result