oj.uz

답안 #523338

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
523338 2022-02-07T13:31:41 Z two_sides Present (RMI21_present) C++17
0 / 100
 498 ms 4128 KB 
#include <bits/stdc++.h>

using namespace std;

const int ODD = 19;
const int EVEN = 18;
const int N = 38;
const int K = 1500000000;

bool good_odd[1 << ODD];
bool good_even[1 << EVEN];
int pre_gcd[N][N], cnt[1 << EVEN];
int match[1 << ODD];

void add(int &x, int y) {
    if (x < K - y) x += y;
    else x = K;
}

void solve() {
    int k; cin >> k; k++;
    int cur_odd = 0, cur_even = 0;
    for (int d = N - 1; d > 0; d--) {
        int t = (d - 1) / 2;
        if (d & 1) {
            if (cur_odd >> t & 1) continue;
        } else {
            if (cur_even >> t & 1) continue;
        }
        for (int nxt_even = 0; nxt_even < (1 << t); nxt_even++)
            cnt[nxt_even] = good_even[nxt_even + cur_even];
        for (int i = 0; i < t; i++)
            for (int mask = 0; mask < (1 << t); mask++)
                if (mask >> i & 1)
                    cnt[mask] += cnt[mask ^ (1 << i)];
        int tmp = 0;
        for (int nxt_odd = 0; nxt_odd < (1 << (d / 2)); nxt_odd++) {
            if (!good_odd[cur_odd + nxt_odd]) continue;
            int nxt_even = match[cur_odd + nxt_odd];
            if ((nxt_even & cur_even) != cur_even) continue;
            add(tmp, cnt[nxt_even & ((1 << t) - 1)]);
        }
        if (tmp < k) {
            k -= tmp;
            if (d & 1) cur_odd += 1 << t;
            else cur_even += 1 << t;
            for (int i = 0; i < ODD; i++)
                if (cur_odd >> i & 1) {
                    int g = pre_gcd[2 * i + 1][d];
                    if (g & 1) cur_odd |= 1 << (g / 2);
                    else cur_even |= 1 << (g / 2 - 1);
                }
            for (int i = 0; i < EVEN; i++)
                if (cur_even >> i & 1) {
                    int g = pre_gcd[2 * i + 2][d];
                    if (g & 1) cur_odd |= 1 << (g / 2);
                    else cur_even |= 1 << (g / 2 - 1);
                }
            
        }
    }
    vector<int> ans;
    for (int i = 0; i < ODD; i++)
        if (cur_odd >> i & 1)
            ans.push_back(2 * i + 1);
    for (int i = 0; i < EVEN; i++)
        if (cur_even >> i & 1)
            ans.push_back(2 * i + 2);
    sort(ans.begin(), ans.end());
    cout << ans.size();
    for (int d : ans)
        cout << ' ' << d;
    cout << '\n';
}

int main() {
    for (int i = 1; i < N; i++)
        for (int j = 1; j < N; j++)
            pre_gcd[i][j] = __gcd(i, j);
    for (int mask = 0; mask < (1 << ODD); mask++) {
        good_odd[mask] = true;
        vector<int> bit;
        for (int i = 0; i < ODD; i++)
            if (mask >> i & 1)
                bit.push_back(2 * i + 1);
        for (int i : bit)
            for (int j : bit)
                if (~mask >> (pre_gcd[i][j] / 2) & 1)
                    good_odd[mask] = false;
        for (int i = 0; i < EVEN; i++) {
            match[mask] += 1 << i;
            for (int j : bit)
                if (~mask >> (pre_gcd[2 * i + 2][j] / 2) & 1) {
                    match[mask] -= 1 << i; break;
                }
        }
    }
    for (int mask = 0; mask < (1 << EVEN); mask++) {
        good_even[mask] = true;
        vector<int> bit;
        for (int i = 0; i < ODD; i++)
            if (mask >> i & 1)
                bit.push_back(2 * i + 2);
        for (int i : bit)
            for (int j : bit)
                if (~mask >> (pre_gcd[i][j] / 2 - 1) & 1)
                    good_even[mask] = false;
    }
    int t; cin >> t;
    while (t--) solve();
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 41.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 16.0

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