oj.uz

Submission #503384

# Submission time Handle Problem Language Result Execution time Memory
503384 2022-01-07T19:00:01 Z Stickfish Present (RMI21_present) C++17
29 / 100
 2130 ms 16208 KB 
#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
using ll = long long;

const int MAXN = 32;
const int MAXK = 1000008;

ll divcnt[MAXN];
ll isgcdcnt[MAXN];
bitset<MAXN> bs;
bitset<MAXN> ans[MAXK];

bool recur(ll& k, vector<ll>& v) {
    int n = v.size();
    int t0 = v[0];
    for (int i = 1; i <= t0; ++i) {
        divcnt[i] = isgcdcnt[i] = bs[i] = 0;
    }
    for (auto t : v)
        bs[t] = 1;
    bool isok = true;
    for (int t = t0; t >= 1; --t) {
        for (int ti = t; ti <= t0; ti += t) {
            //if (ti % t == 0) {
                divcnt[t] += bs[ti];
                isgcdcnt[t] -= isgcdcnt[ti];
            //}
        }
        isgcdcnt[t] += divcnt[t] * (divcnt[t] - 1);
        if (!bs[t] && isgcdcnt[t] > 0) {
            isok = false;
            break;
        }
    }
    if (isok) {
        ans[k++] = bs;
        if (k >= MAXK)
            return true;
    }
    int x = v.back();
    for (int t = 1; t < x; ++t) {
        v.push_back(t);
        if (recur(k, v))
            return true;
        v.pop_back();
    }
    return false;
}

void solve() {
    ll k;
    cin >> k;
    if (k == 0) {
        cout << 0 << endl;
        return;
    }
    --k;
    cout << ans[k].count() << ' ';
    for (int t = 1; t < MAXN; ++t) {
        if (ans[k][t])
            cout << t << ' ';
    }
    cout << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    vector<ll> ans;
    ll k = 0;
    for (int t = 1;; ++t) {
        ans.push_back(t);
        if (recur(k, ans)) {
            break;
        }
        ans.pop_back();
    }
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Compilation message

Main.cpp: In function 'bool recur(ll&, std::vector<long long int>&)':
Main.cpp:17:9: warning: unused variable 'n' [-Wunused-variable]
   17 |     int n = v.size();
      |         ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2083 ms 8056 KB Output is correct
2 Correct 2024 ms 8008 KB Output is correct
3 Correct 2085 ms 7996 KB Output is correct
4 Correct 2073 ms 8000 KB Output is correct
5 Correct 2098 ms 8004 KB Output is correct
6 Correct 2130 ms 7996 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2083 ms 8056 KB Output is correct
2 Correct 2024 ms 8008 KB Output is correct
3 Correct 2085 ms 7996 KB Output is correct
4 Correct 2073 ms 8000 KB Output is correct
5 Correct 2098 ms 8004 KB Output is correct
6 Correct 2130 ms 7996 KB Output is correct
7 Correct 2114 ms 8092 KB Output is correct
8 Correct 2048 ms 8328 KB Output is correct
9 Correct 2061 ms 8196 KB Output is correct
10 Correct 2044 ms 8332 KB Output is correct
11 Correct 2082 ms 8028 KB Output is correct
12 Correct 1988 ms 8092 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2083 ms 8056 KB Output is correct
2 Correct 2024 ms 8008 KB Output is correct
3 Correct 2085 ms 7996 KB Output is correct
4 Correct 2073 ms 8000 KB Output is correct
5 Correct 2098 ms 8004 KB Output is correct
6 Correct 2130 ms 7996 KB Output is correct
7 Correct 2114 ms 8092 KB Output is correct
8 Correct 2048 ms 8328 KB Output is correct
9 Correct 2061 ms 8196 KB Output is correct
10 Correct 2044 ms 8332 KB Output is correct
11 Correct 2082 ms 8028 KB Output is correct
12 Correct 1988 ms 8092 KB Output is correct
13 Runtime error 2063 ms 16208 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 2083 ms 8056 KB Output is correct
2 Correct 2024 ms 8008 KB Output is correct
3 Correct 2085 ms 7996 KB Output is correct
4 Correct 2073 ms 8000 KB Output is correct
5 Correct 2098 ms 8004 KB Output is correct
6 Correct 2130 ms 7996 KB Output is correct
7 Correct 2114 ms 8092 KB Output is correct
8 Correct 2048 ms 8328 KB Output is correct
9 Correct 2061 ms 8196 KB Output is correct
10 Correct 2044 ms 8332 KB Output is correct
11 Correct 2082 ms 8028 KB Output is correct
12 Correct 1988 ms 8092 KB Output is correct
13 Runtime error 2063 ms 16208 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 2083 ms 8056 KB Output is correct
2 Correct 2024 ms 8008 KB Output is correct
3 Correct 2085 ms 7996 KB Output is correct
4 Correct 2073 ms 8000 KB Output is correct
5 Correct 2098 ms 8004 KB Output is correct
6 Correct 2130 ms 7996 KB Output is correct
7 Correct 2114 ms 8092 KB Output is correct
8 Correct 2048 ms 8328 KB Output is correct
9 Correct 2061 ms 8196 KB Output is correct
10 Correct 2044 ms 8332 KB Output is correct
11 Correct 2082 ms 8028 KB Output is correct
12 Correct 1988 ms 8092 KB Output is correct
13 Runtime error 2063 ms 16208 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -