oj.uz

답안 #503320

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
503320 2022-01-07T16:24:09 Z atoiz Present (RMI21_present) C++14
0 / 100
 1 ms 204 KB 
#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; odd += 2) {
				if (on(odd_mask, odd / 2) && !on(odd_mask, gcd_val[odd][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 (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;
	while (t--) {
		int64_t x; cin >> x;

		vector<int> vec = {};
		int lo = 0, hi = 37;
		while (x) {
			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
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -