| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 503320 |
2022-01-07T16:24:09 Z |
atoiz |
Present (RMI21_present) |
C++14 |
|
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;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
