Submission #795078

#	Time	Username	Problem	Language	Result	Execution time	Memory
795078		PurpleCrayon	Present (RMI21_present)	C++17	100 / 100	1762 ms	5580 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 1e2, MOD = 1e9+7;
const int K = 19;
 
int g[N][N], allow[1 << K];
bool can_odd[1 << K];
bool can_ev[1 << K];

void pre() {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            g[i][j] = gcd(i, j);

    can_odd[0] = 1;
    for (int mask = 1; mask < (1 << K); mask++) {
        int k = 31 - __builtin_clz(mask);
        if (!can_odd[mask ^ (1 << k)]) continue;

        can_odd[mask] = 1;
        for (int j = 0; j < k; j++) if ((mask >> j) & 1) {
            int x = g[2 * k + 1][2 * j + 1];
            assert(x % 2 == 1); x /= 2;
            if ((mask >> x) & 1 ^ 1) {
                can_odd[mask] = 0;
                break;
            }
        }
    }

    can_ev[0] = 1;
    for (int mask = 1; mask < (1 << K); mask++) {
        int k = 31 - __builtin_clz(mask);
        if (!can_ev[mask ^ (1 << k)]) continue;

        can_ev[mask] = 1;
        for (int j = 0; j < k; j++) if ((mask >> j) & 1) {
            int x = g[2 * k + 2][2 * j + 2];
            assert(x % 2 == 0); x /= 2; x--;
            if ((mask >> x) & 1 ^ 1) {
                can_ev[mask] = 0;
                break;
            }
        }
    }


    for (int mask = 0; mask < (1 << K); mask++) if (can_odd[mask]) {
        int me = 0;
        for (int i = 0; i < K; i++) {
            if ((mask >> i) & 1) {
                me |= 1 << i;
                continue;
            }

            bool bad = 0;
            for (int j = 0; j < K; j++) if ((mask >> j) & 1) {
                int x = g[2 * i + 1][2 * j + 1];
                assert(x % 2 == 1); x /= 2;
                if ((mask >> x) & 1 ^ 1) {
                    bad = 1;
                    break;
                }
            }

            if (!bad) me |= 1 << i;
        }

        allow[mask] = me;
    }
}

int sum[1 << K];

void solve() {
    ll n; cin >> n;

    int ev_mask = 0, odd_mask = 0;
    int cnt_odd = 0, cnt_ev = 0;
    for (int use = 2 * K; use >= 1; use--) {
        memset(sum, 0, sizeof(sum));
        if (use % 2) cnt_odd++;
        else cnt_ev++;

        for (int i = 0; i < (1 << K); i++) {
            if (!can_odd[i]) continue;
            if ((odd_mask >> (K - cnt_odd)) != (i >> (K - cnt_odd))) continue;
            sum[allow[i]]++;
        }

        for (int i = 0; i < K; i++) {
            for (int j = 0; j < (1 << K); j++) if ((j >> i) & 1 ^ 1) {
                sum[j] += sum[j ^ (1 << i)];
            }
        }

        ll cnt_can = 0;
        for (int mask = 0; mask < (1 << K); mask++) {
            if (!can_ev[mask]) continue;
            if ((ev_mask >> (K - cnt_ev)) != (mask >> (K - cnt_ev))) continue;

            int cur = 0;
            for (int i = 0; i < K; i++) if ((mask >> i) & 1) {
                int me = 2 * i + 2; me >>= __builtin_ctz(me); 
                assert(me % 2 == 1); me /= 2;
                cur |= 1 << me;
            }

            cnt_can += sum[cur];
        }

        if (cnt_can > n) { // can skip
        } else {
            if (use % 2) odd_mask |= 1 << (use / 2);
            else ev_mask |= 1 << (use / 2 - 1);
            n -= cnt_can;
        }
    }

    vector<int> ans;
    for (int i = 0; i < K; i++) if ((ev_mask >> i) & 1)
        ans.push_back(2 * i + 2);

    for (int i = 0; i < K; i++) if ((odd_mask >> i) & 1)
        ans.push_back(2 * i + 1);

    sort(ans.begin(), ans.end());
    cout << sz(ans);
    for (int x : ans) cout << ' ' << x;
    cout << '\n';
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    pre();
    int T = 1;
    cin >> T;
    while (T--) solve();
}

Compilation message (stderr)

Main.cpp: In function 'void pre()':
Main.cpp:28:29: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   28 |             if ((mask >> x) & 1 ^ 1) {
      |                 ~~~~~~~~~~~~^~~
Main.cpp:44:29: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   44 |             if ((mask >> x) & 1 ^ 1) {
      |                 ~~~~~~~~~~~~^~~
Main.cpp:64:33: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   64 |                 if ((mask >> x) & 1 ^ 1) {
      |                     ~~~~~~~~~~~~^~~
Main.cpp: In function 'void solve()':
Main.cpp:96:61: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   96 |             for (int j = 0; j < (1 << K); j++) if ((j >> i) & 1 ^ 1) {
      |                                                    ~~~~~~~~~^~~

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