oj.uz

Submission #643356

# Submission time Handle Problem Language Result Execution time Memory
643356 2022-09-21T19:55:09 Z Matteo_Verz Present (RMI21_present) C++17
29 / 100
 3964 ms 16524 KB 
#include <bits/stdc++.h>
#ifdef BLAT
   #include "debug/debug.hpp"
#else
   #define debug(x...)
#endif

using namespace std;

void printSet(long long set, int setidx = 0) {
    // cout << "S" << setidx << " = ";
    cout << __builtin_popcountll(set) << ' ';
    for (int i = 1; i <= 40; i++)
        if (set & (1LL << i))
            cout << i << ' ';
    cout << endl;
}

void generateNextSet(long long &mask) {
    for (int i = 1; i <= 40; i++) {
        mask ^= (1LL << i);
        if (mask & (1LL << i)) {
            break;
        }
    }

    queue <int> q;
    for (int i = 1; i <= 40; i++)
        for (int j = 1; j <= 40; j++)
            if ((mask & (1LL << i)) && (mask & (1LL << j))) {
                int g = __gcd(i, j);
                if (!(mask & (1LL << g))) {
                    mask |= (1LL << g);
                    q.push(g);
                }
            }

    while (q.size()) {
        int fr = q.front();
        q.pop();

        for (int i = 1; i <= 40; i++)
            if ((mask & (1LL << i))) {
                int g = __gcd(fr, i);
                if (!(mask & (1LL << g))) {
                    mask |= (1LL << g);
                    q.push(g);
                }
            }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long set = 2;
    vector <long long> sets = {0};
    for (int i = 1; i <= 1000000; i++) {
        sets.push_back(set);
        generateNextSet(set);
    }

    debug(sets.size());
    int t;
    cin >> t;
    while (t--) {
        int k;
        cin >> k;
        printSet(sets[k]);
    }
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3938 ms 8940 KB Output is correct
2 Correct 3964 ms 8888 KB Output is correct
3 Correct 3905 ms 8856 KB Output is correct
4 Correct 3912 ms 8716 KB Output is correct
5 Correct 3894 ms 8740 KB Output is correct
6 Correct 3905 ms 8576 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3938 ms 8940 KB Output is correct
2 Correct 3964 ms 8888 KB Output is correct
3 Correct 3905 ms 8856 KB Output is correct
4 Correct 3912 ms 8716 KB Output is correct
5 Correct 3894 ms 8740 KB Output is correct
6 Correct 3905 ms 8576 KB Output is correct
7 Correct 3895 ms 8716 KB Output is correct
8 Correct 3879 ms 8832 KB Output is correct
9 Correct 3890 ms 8628 KB Output is correct
10 Correct 3887 ms 8880 KB Output is correct
11 Correct 3888 ms 8672 KB Output is correct
12 Correct 3913 ms 8584 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3938 ms 8940 KB Output is correct
2 Correct 3964 ms 8888 KB Output is correct
3 Correct 3905 ms 8856 KB Output is correct
4 Correct 3912 ms 8716 KB Output is correct
5 Correct 3894 ms 8740 KB Output is correct
6 Correct 3905 ms 8576 KB Output is correct
7 Correct 3895 ms 8716 KB Output is correct
8 Correct 3879 ms 8832 KB Output is correct
9 Correct 3890 ms 8628 KB Output is correct
10 Correct 3887 ms 8880 KB Output is correct
11 Correct 3888 ms 8672 KB Output is correct
12 Correct 3913 ms 8584 KB Output is correct
13 Runtime error 3897 ms 16524 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3938 ms 8940 KB Output is correct
2 Correct 3964 ms 8888 KB Output is correct
3 Correct 3905 ms 8856 KB Output is correct
4 Correct 3912 ms 8716 KB Output is correct
5 Correct 3894 ms 8740 KB Output is correct
6 Correct 3905 ms 8576 KB Output is correct
7 Correct 3895 ms 8716 KB Output is correct
8 Correct 3879 ms 8832 KB Output is correct
9 Correct 3890 ms 8628 KB Output is correct
10 Correct 3887 ms 8880 KB Output is correct
11 Correct 3888 ms 8672 KB Output is correct
12 Correct 3913 ms 8584 KB Output is correct
13 Runtime error 3897 ms 16524 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3938 ms 8940 KB Output is correct
2 Correct 3964 ms 8888 KB Output is correct
3 Correct 3905 ms 8856 KB Output is correct
4 Correct 3912 ms 8716 KB Output is correct
5 Correct 3894 ms 8740 KB Output is correct
6 Correct 3905 ms 8576 KB Output is correct
7 Correct 3895 ms 8716 KB Output is correct
8 Correct 3879 ms 8832 KB Output is correct
9 Correct 3890 ms 8628 KB Output is correct
10 Correct 3887 ms 8880 KB Output is correct
11 Correct 3888 ms 8672 KB Output is correct
12 Correct 3913 ms 8584 KB Output is correct
13 Runtime error 3897 ms 16524 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -