Submission #503343

#	Time	Username	Problem	Language	Result	Execution time	Memory
503343		atoiz	Present (RMI21_present)	C++14	100 / 100	3071 ms	2344 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int max_val;
vector<int> chosen;
int arr[1 << 20], gcd_val[50][50];
int64_t cnt;

bool on(int mask, int i) { return (mask >> i) & 1; }
int& toggle(int &mask, int i) { return mask ^= 1 << i; }

void proc_odd(int val, int forced_mask, int odd_mask) {
	if (val < 0) {
		int mask = 0;
		for (int even = 2; even <= max_val; even += 2) {
			bool good = true;

			for (int odd = 1; odd <= max_val && good; odd += 2) {
				if (on(odd_mask, odd / 2) && !on(odd_mask, gcd_val[odd][even] / 2)) {
					good = false;
					break;
				}
			}

			if (good) for (int oth : chosen) {
				if ((gcd_val[oth][even] & 1) && !on(odd_mask, gcd_val[oth][even] / 2)) {
					good = false;
					break;
				}
			}

			if (good) toggle(mask, even / 2);
		}
		++arr[mask];
		return;
	}

	if (!on(forced_mask, val / 2)) proc_odd(val - 2, forced_mask, odd_mask);
	toggle(odd_mask, val / 2);
	for (int odd = val + 2; odd <= max_val; odd += 2) {
		if (on(odd_mask, odd / 2) && not on(forced_mask, gcd_val[odd][val] / 2)) {
			toggle(forced_mask, gcd_val[odd][val] / 2);
		}
	}
	for (int oth : chosen) {
		if (not on(forced_mask, gcd_val[oth][val] / 2)) {
			toggle(forced_mask, gcd_val[oth][val] / 2);
		}
	}
	proc_odd(val - 2, forced_mask, odd_mask);
}

void calc_sum() {
	int n = max_val / 2 + 1;
	for (int k = 0; k < n; ++k) {
		for (int i = 0; i < (1 << n); ++i) {
			if (!((i >> k) & 1)) {
				arr[i] += arr[i ^ (1 << k)];
			}
		}
	}
}

void proc_even(int val, int forced_mask, int even_mask) {
	if (val == 0) {
		cnt += arr[even_mask];
		return;
	}

	if (!on(forced_mask, val / 2)) proc_even(val - 2, forced_mask, even_mask);
	toggle(even_mask, val / 2);
	for (int even = val + 2; even <= max_val; even += 2) {
		if (on(even_mask, even / 2) && not on(forced_mask, gcd_val[even][val] / 2)) {
			toggle(forced_mask, gcd_val[even][val] / 2);
		}
	}
	for (int oth : chosen) if (oth % 2 == 0) {
		if (not on(forced_mask, gcd_val[oth][val] / 2)) {
			toggle(forced_mask, gcd_val[oth][val] / 2);
		}
	}
	proc_even(val - 2, forced_mask, even_mask);
}

int64_t calc(int val, vector<int> vec) {
	max_val = val;
	chosen = vec;
	cnt = 0;
	memset(arr, 0, sizeof(int) * (1 << (max_val / 2 + 1)));

	int forced_odd = 0, forced_even = 0;
	for (int i : vec) for (int j : vec) {
		int k = gcd_val[i][j];
		if (val < k && k < *min_element(vec.begin(), vec.end())) return 0;
		if (k & 1) forced_odd |= 1 << (k / 2);
		else forced_even |= 1 << (k / 2);
	}

	proc_odd(max_val - !(max_val & 1), forced_odd, 0);
	calc_sum();
	proc_even(max_val - (max_val & 1), forced_even, 0);
	return cnt;
}

int main() {
	for (int i = 1; i < 50; ++i) {
		for (int j = 1; j < 50; ++j) {
			gcd_val[i][j] = __gcd(i, j);
		}
	}

	int t; cin >> t;
	// t = 100;
	while (t--) {
		int64_t x; cin >> x;
		// x = 99 - t;

		vector<int> vec = {};
		int lo = 0, hi = 37;
		while (x) {
			// cout << "x = " << x << ", lo = " << lo << ", hi = " << hi << endl;
			while (lo < hi) {
				int mid = (lo + hi + 1) / 2;
				int64_t cur = calc(mid, vec);
				if (cur <= x) lo = mid;
				else hi = mid - 1;
			}
			x -= calc(hi, vec);
			vec.push_back(hi + 1);

			lo = 0;
		}

		if (!vec.empty()) for (int k = vec.back() - 1; k >= 1; --k) {
			bool cont = true;
			for (int i = (int) vec.size() - 1; i >= 0; --i) {
				for (int j = i - 1; j >= 0; --j) if (k == gcd_val[vec[i]][vec[j]]) {
					vec.push_back(k);
					cont = false;
					break;
				}
				if (!cont) break;
			}
		}

		reverse(vec.begin(), vec.end());
		cout << vec.size();
		for (auto i : vec) cout << ' ' << i;
		cout << endl;
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 21 / 21
• Subtask 3: 41 / 41
• Subtask 4: 14 / 14
• Subtask 5: 16 / 16