QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#622318#8790. First BillionBlackPandaCompile Error//C++143.9kb2024-10-08 20:51:442024-10-08 20:51:44

Judging History

你现在查看的是最新测评结果

  • [2024-10-08 20:51:44]
  • 评测
  • [2024-10-08 20:51:44]
  • 提交

answer

// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "\033[32m[" << __LINE__ << "]\033[0m "
#define SZ(x) ((int) x.size() - 1)
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
template <typename T> T& read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x *= f;
}
const int N = 110, T = 1e5, M = 100 * T + 10, L = 1e9;
int n, w[N];
pair <int, int> g[N];
bitset <M> f[N];
// pair <int, int> a[N];
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l, int r) {return mrand() % (r - l + 1) + l;}
int sum1, sum2;
// void dfs(int x, int sum) {
// 	if (x == n + 1) return;
// 	if (sum)
// }
unordered_map <int, ll> mp1, mp2;
void solve(ll x, ll y) {
	vector <int> ans;
	int s = 0;
	F(i, 1, n / 2)
		if (x & (1ll << (i - 1))) {
			s += g[i].first;
			ans.push_back(g[i].second);
		}
	F(i, n / 2 + 1, n)
		if (!(y & (1ll << (n - i)))) {
			s += g[i].first;
			ans.push_back(g[i].second);
		}
	assert(s == L);
	sort(all(ans));
	cout << ans.size() << ' ';
	for (int i: ans) cout << i << ' ';
	// cout << s;
	exit(0);
}
signed main() {
	read(n);
	// int s = 0;
	F(i, 1, n) read(g[i].first), g[i].second = i;//read(a[i].first), a[i].second = i;
	shuffle(g + 1, g + n + 1, mrand);
	F(i, 1, n / 2) sum1 += g[i].first;
	F(i, n / 2 + 1, n) sum2 += g[i].first;
	deque <tuple <int, int, ll>> s1, s2;
	s1.emplace_back(1, 0, 0);
	s2.emplace_back(n, 0, 0);
	while (true) {
		{
			auto [a, b, c] = s1.front(); s1.pop_front();
			if (a == n / 2 + 1) {
				int w = sum1 - b * 2;
				if (mp2.count(w)) solve(c, mp2[w]);
				mp1[w] = c;
			} else {
				if ((b + g[a].first) * 2 <= sum1) {
					s1.emplace_front(a + 1, b + g[a].first, c | (1ll << (a - 1)));
					s1.emplace_back(a + 1, b, c);
				} else s1.emplace_front(a + 1, b, c);
			}
		}
		{
			auto [a, b, c] = s2.front(); s2.pop_front();
			if (a == n / 2) {
				int w = sum2 - b * 2;
				if (mp1.count(w)) solve(mp1[w], c);
				mp2[w] = c;
			} else {
				if ((b + g[a].first) * 2 <= sum2) {
					s2.emplace_front(a - 1, b + g[a].first, c | (1ll << (n - a)));
					s2.emplace_back(a - 1, b, c);
				} else s2.emplace_front(a - 1, b, c);
			}
		}
	}
	// dfs(1, 0);
	// shuffle(g + 1, g + n + 1, mrand);
	// int ss = 0;
	// F(i, 1, n / 2) {
	// 	ss += g[i] % T;
	// }
	// debug << ss << endl;
	// sort(g + 1, g + n + 1);
	// reverse(g + 1, g + n + 1);
	// f[0][0] = true;
	// while (true) {
		// F(i, 1, n) {
		// 	// f[i].reset();
		// 	w[i] = g[i].first % T;
		// 	f[i] = f[i - 1] | (f[i - 1] << w[i]);
		// 	// s += w[i];
		// 	// F(j, 0, s) {
		// 	// 	f[i][j] = f[i - 1][j];
		// 	// 	if (j >= w[i] && f[i - 1][j - w[i]]) {
		// 	// 		f[i][j] = true;
		// 	// 	}
		// 	// }
		// }
		// // cout << w[2] + w[3] + w[4] + w[8] + w[10] << " " << f[n][30000] << endl;
		// F(i, 1, 100) {
		// 	if (f[n][i * T]) {
		// 		// debug << i << endl;
		// 		vector <int> g;
		// 		int s = i * T, sum = 0;
		// 		DF(j, n, 1) {
		// 			if (s >= w[j] && f[j - 1][s - w[j]] && sum + ::g[j].first <= L) {
		// 				sum += ::g[j].first;
		// 				g.push_back(::g[j].second);
		// 				s -= w[j];
		// 			}
		// 		}
		// 		debug << sum << " " << L << endl;// << " " << s << endl;
		// 		if (sum == L) {
		// 			cout << g.size() << ' ';
		// 			sort(all(g));
		// 			for (int i: g) cout << i << ' ';
		// 			return 0;
		// 		}
		// 	}
		// }
	// }
	// assert(false);
	// F(i, 1, n)
	return 0;
}
/* why?

詳細信息

answer.code:141:1: error: unterminated comment
  141 | /* why?
      | ^
answer.code: In function ‘int main()’:
answer.code:65:30: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   65 |                         auto [a, b, c] = s1.front(); s1.pop_front();
      |                              ^
answer.code:78:30: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   78 |                         auto [a, b, c] = s2.front(); s2.pop_front();
      |                              ^