제출 #523349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
523349		two_sides	Present (RMI21_present)	C++17	100 / 100	527 ms	4420 KiB

Main

#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;
        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;           
        }
    }
    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: 8 / 8
• Subtask 2: 21 / 21
• Subtask 3: 41 / 41
• Subtask 4: 14 / 14
• Subtask 5: 16 / 16