Submission #498645

#	Time	Username	Problem	Language	Result	Execution time	Memory
498645		model_code	Present (RMI21_present)	C++17	0 / 100	1599 ms	524292 KiB

Main

// 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));
    }
}

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