// present_70_tamio.cpp
#include <bits/stdc++.h>
using namespace std;
constexpr int b = 13;
void print_msk(long long x) {
cout << __builtin_popcount(x) << ' ';
for (int i = 0; i < 3 * b; ++i)
if ((x >> i) & 1) cout << i + 1 << ' ';
cout << endl;
}
using ll = long long;
long long the_gcd[3 * b + 5][3 * b + 5], d[1 << (2 * b)];
bool ok_set[1 << (2 * b)], rel_okset[b][1 << (2 * b)];
uint64_t rel_okmask[1 << (2 * b)];
static void mk_gcd() {
for (int i = 1; i <= 3 * b; ++i)
for (int j = 1; j <= 3 * b; ++j) the_gcd[i][j] = __gcd(i, j);
}
static void build_rel_okset(int x, int curr_nr = 1, int state = 0) {
if (curr_nr == 2 * b + 1) {
rel_okset[x - 2 * b - 1][state / 2] = 1;
return;
}
build_rel_okset(x, curr_nr + 1, state);
for (int i = 1; i < curr_nr; ++i)
if (((state >> i) & 1) && !((state >> the_gcd[i][curr_nr]) & 1)) return;
state |= (1 << curr_nr);
if ((state >> the_gcd[curr_nr][x]) & 1)
build_rel_okset(x, curr_nr + 1, state);
}
static void build_rel_okmask() {
for (int i = 0; (i >> (2 * b)) == 0; ++i)
for (int j = 0; j < b; ++j)
if (rel_okset[j][i]) rel_okmask[i] |= (1 << j);
}
static void build_okset(int curr_nr = 1, int state = 0) {
if (curr_nr == 2 * b + 1) {
ok_set[state / 2] = 1;
return;
}
build_okset(curr_nr + 1, state);
for (int i = 1; i < curr_nr; ++i)
if (((state >> i) & 1) && !((state >> the_gcd[i][curr_nr]) & 1)) return;
build_okset(curr_nr + 1, state | (1ull << curr_nr));
}
// d[xy] = cate moduri de a seta prefixele de 2b numerele dau cel putin
// gcd-urile din x, si sunt OK cu cel putin numerele din y
static void mk_d() {
for (int i = 0; (i >> (2 * b)) == 0; ++i) {
if (!ok_set[i]) continue;
int msk = i & ((1 << b) - 1);
for (int x = 2 * b + 1; x <= 3 * b; ++x)
if (rel_okset[x - 2 * b - 1][i]) msk |= 1 << (x - b - 1);
++d[msk];
}
for (int i = 0; i < 2 * b; ++i)
for (int msk = 0; (msk >> (2 * b)) == 0; ++msk)
if ((msk >> i) & 1)
d[msk ^ (1 << i)] += d[msk];
else
msk += (1 << i) - 1;
}
// gets d mask for 2b+1 ... 3b of x
static long long get_msk(long long x) {
int msk = x << b;
for (int i = 2 * b + 1; i <= 3 * b; ++i)
if ((x >> (i - 2 * b - 1)) & 1)
for (int j = i + 1; j <= 3 * b; ++j)
if ((x >> (j - 2 * b - 1)) & 1) msk |= 1 << (the_gcd[i][j] - 1);
return msk;
}
static long long find_top_bits(long long &k) {
for (long long i = 0;; ++i) {
long long current = d[get_msk(i)];
if (k >= current)
k -= current;
else
return i << (2 * b);
}
}
static long long find_low_bits(long long k, long long h) {
ll gcds = 0;
for (int i = 2 * b + 1; i <= 3 * b; ++i)
if ((h >> (i - 1)) & 1)
for (int j = i + 1; j <= 3 * b; ++j)
if ((h >> (j - 1)) & 1) gcds |= 1 << (the_gcd[i][j] - 1);
for (long long l = 0;; ++l) {
if (!ok_set[l]) continue;
if ((l | gcds) != l) continue;
if ((rel_okmask[l] | (h >> (2 * b))) != rel_okmask[l]) continue;
if (k == 0) return l | h;
--k;
}
}
static long long solve(long long k) {
long long h = find_top_bits(k);
return find_low_bits(k, h);
}
int main() {
mk_gcd();
for (int i = 2 * b + 1; i <= 3 * b; ++i) build_rel_okset(i);
build_okset();
build_rel_okmask();
mk_d();
int t;
cin >> t;
while (t--) {
int k;
cin >> k;
print_msk(solve(k));
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1599 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1599 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1599 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1599 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1599 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
