oj.uz

Submission #523349

# Submission time Handle Problem Language Result Execution time Memory
523349 2022-02-07T14:09:55 Z two_sides Present (RMI21_present) C++17
100 / 100
 527 ms 4420 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;
        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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 4036 KB Output is correct
2 Correct 523 ms 4052 KB Output is correct
3 Correct 503 ms 4164 KB Output is correct
4 Correct 507 ms 4116 KB Output is correct
5 Correct 513 ms 4420 KB Output is correct
6 Correct 508 ms 4084 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 4036 KB Output is correct
2 Correct 523 ms 4052 KB Output is correct
3 Correct 503 ms 4164 KB Output is correct
4 Correct 507 ms 4116 KB Output is correct
5 Correct 513 ms 4420 KB Output is correct
6 Correct 508 ms 4084 KB Output is correct
7 Correct 511 ms 4232 KB Output is correct
8 Correct 527 ms 4208 KB Output is correct
9 Correct 512 ms 4104 KB Output is correct
10 Correct 509 ms 4076 KB Output is correct
11 Correct 506 ms 4040 KB Output is correct
12 Correct 506 ms 4036 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 4036 KB Output is correct
2 Correct 523 ms 4052 KB Output is correct
3 Correct 503 ms 4164 KB Output is correct
4 Correct 507 ms 4116 KB Output is correct
5 Correct 513 ms 4420 KB Output is correct
6 Correct 508 ms 4084 KB Output is correct
7 Correct 511 ms 4232 KB Output is correct
8 Correct 527 ms 4208 KB Output is correct
9 Correct 512 ms 4104 KB Output is correct
10 Correct 509 ms 4076 KB Output is correct
11 Correct 506 ms 4040 KB Output is correct
12 Correct 506 ms 4036 KB Output is correct
13 Correct 519 ms 4084 KB Output is correct
14 Correct 510 ms 4132 KB Output is correct
15 Correct 513 ms 4036 KB Output is correct
16 Correct 508 ms 4164 KB Output is correct
17 Correct 504 ms 4112 KB Output is correct
18 Correct 509 ms 4028 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 4036 KB Output is correct
2 Correct 523 ms 4052 KB Output is correct
3 Correct 503 ms 4164 KB Output is correct
4 Correct 507 ms 4116 KB Output is correct
5 Correct 513 ms 4420 KB Output is correct
6 Correct 508 ms 4084 KB Output is correct
7 Correct 511 ms 4232 KB Output is correct
8 Correct 527 ms 4208 KB Output is correct
9 Correct 512 ms 4104 KB Output is correct
10 Correct 509 ms 4076 KB Output is correct
11 Correct 506 ms 4040 KB Output is correct
12 Correct 506 ms 4036 KB Output is correct
13 Correct 519 ms 4084 KB Output is correct
14 Correct 510 ms 4132 KB Output is correct
15 Correct 513 ms 4036 KB Output is correct
16 Correct 508 ms 4164 KB Output is correct
17 Correct 504 ms 4112 KB Output is correct
18 Correct 509 ms 4028 KB Output is correct
19 Correct 506 ms 4104 KB Output is correct
20 Correct 507 ms 4132 KB Output is correct
21 Correct 505 ms 4064 KB Output is correct
22 Correct 503 ms 4036 KB Output is correct
23 Correct 510 ms 4128 KB Output is correct
24 Correct 514 ms 4088 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 4036 KB Output is correct
2 Correct 523 ms 4052 KB Output is correct
3 Correct 503 ms 4164 KB Output is correct
4 Correct 507 ms 4116 KB Output is correct
5 Correct 513 ms 4420 KB Output is correct
6 Correct 508 ms 4084 KB Output is correct
7 Correct 511 ms 4232 KB Output is correct
8 Correct 527 ms 4208 KB Output is correct
9 Correct 512 ms 4104 KB Output is correct
10 Correct 509 ms 4076 KB Output is correct
11 Correct 506 ms 4040 KB Output is correct
12 Correct 506 ms 4036 KB Output is correct
13 Correct 519 ms 4084 KB Output is correct
14 Correct 510 ms 4132 KB Output is correct
15 Correct 513 ms 4036 KB Output is correct
16 Correct 508 ms 4164 KB Output is correct
17 Correct 504 ms 4112 KB Output is correct
18 Correct 509 ms 4028 KB Output is correct
19 Correct 506 ms 4104 KB Output is correct
20 Correct 507 ms 4132 KB Output is correct
21 Correct 505 ms 4064 KB Output is correct
22 Correct 503 ms 4036 KB Output is correct
23 Correct 510 ms 4128 KB Output is correct
24 Correct 514 ms 4088 KB Output is correct
25 Correct 523 ms 4104 KB Output is correct
26 Correct 512 ms 4112 KB Output is correct
27 Correct 504 ms 4036 KB Output is correct
28 Correct 511 ms 4160 KB Output is correct
29 Correct 515 ms 4132 KB Output is correct
30 Correct 501 ms 4056 KB Output is correct