oj.uz

Submission #643703

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

using namespace std;

const int K = 1500000000;

vector <vector <short>> generateGCD() {
    vector <vector <short>> gcd(40, vector <short>(40));
    for (int i = 0; i < 40; i++)
        for (int j = 0; j < 40; j++)
            gcd[i][j] = gcd[j][i] = __gcd(i, j);
    
    return gcd;
}

void generateNextSet(vector <int> &set, vector <vector <short>> &gcd) {
    int lastdeleted = 0;
    while (true) {
        if (set.empty() || set.back() > lastdeleted + 1) {
            set.push_back(lastdeleted + 1);
            break;
        }
        lastdeleted = set.back();
        set.pop_back();
    }

    long long mask = 0;
    for (int i = 0; i < set.size(); i++)
        mask |= (1LL << set[i]);

    for (int i = 0; i < set.size(); i++)
        for (int j = i + 1; j < set.size(); j++) {
            int g = gcd[set[i]][set[j]];
            if (!(mask & (1LL << g))) {
                mask |= (1LL << g);
                set.push_back(g);
            }
        }

    sort(set.begin(), set.end(), greater <int>());
}

long long convertSet(vector <int> &set) {
    long long mask = 0;
    for (auto it : set)
        mask |= (1LL << it);
    return mask;
}

vector <int> convertSet(long long mask) {
    vector <int> set;
    for (int i = 1; (1LL << i) <= mask; i++)
        if (mask & (1LL << i))
            set.push_back(i);
    
    return set;
}

void printSet(vector <int> &set) {
    cout << set.size() << ' ';
    for (int i = set.size() - 1; i >= 0; i--)
        cout << set[i] << ' ';
    cout << '\n';
}

vector <long long> generatedSets = {0, 568869022, 1233560558, 2272459518, 2860715134, 3802010750, 4703447038, 5530260478, 6711137022, 7479096318, 8760440894, 9743567262, 11109386494, 12293590078, 13592234158, 15242495774, 16705357310, 17637718526, 18283513182, 19398815646, 19986434814, 20897329150, 21824980478, 22657821694, 23862084350, 24653081598, 25949054974, 26987349502, 28384882686, 29626903422, 30918381566, 32595873278, 34230980350, 35452809454, 37109426670, 38813461502, 40819684286, 42560270190, 44839782638, 47245347566, 49868414398, 52085194934, 53767349302, 55165068734, 56889374462, 58815178686, 60968491454, 63308381118, 66209991662, 68828905790, 70062610174, 71502279006, 73211754366, 74961136254, 76316640510, 78394726014, 80606604670, 83360099198, 85970003774, 87090968318, 88663961694, 90373063550, 92149810942, 93581623166, 95708623742, 98059967870, 100946845438, 103448677118, 106044421630, 109560249086, 112814922494, 117342967294, 121160866494, 124355384830, 127419495294, 131560184702, 136190008318, 137913853446, 138531040638, 139644987902, 140219805518, 141017297366, 142013600698, 142807763238, 144025530134, 144763354198, 146090048894, 146980490654, 148393757342, 149409532638, 150892755870, 152538691742, 153755566926, 154957408462, 155580029086, 156770764966, 157358404414, 158097495678, 159146733006, 159933467230, 161185139022, 161940566430, 163276212046, 164221176478, 165635295438, 166774957694, 168181271374, 169853018958, 171335114078, 172643326390, 174357744562, 176098443686, 177809919462, 179546109310, 181741699838, 184148501822, 186947079598, 189283620094, 190950559222, 192250809198, 194046763838, 196044024270, 198168226302, 200426942382, 203012935342, 206167614230, 207170931518, 208845552410, 210481256350, 211906254462, 213486431446, 215552596862, 217726328478, 220138208094, 223103122910, 224267081342, 225974820574, 227648311646, 229118929758, 230695347518, 232800835742, 235023840926, 237739335294, 240592681662, 243216983358, 246187865598, 249721139278, 254020225694, 258306306454, 261025343102, 264501359518};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    vector <int> set = {1};
    auto gcd = generateGCD();

    int t;
    cin >> t;
    while (t--) {
        int k;
        cin >> k;
        if (k == 0) cout << 0 << '\n';
        else {
            int idx = k / 10000000;
            int setidx = idx * 10000000;
            vector <int> set = convertSet(generatedSets[idx]);

            while (setidx < k) {
                setidx++;
                generateNextSet(set, gcd);
            }

            printSet(set);
        }
    }
    return 0;
}

Compilation message

Main.cpp: In function 'void generateNextSet(std::vector<int>&, std::vector<std::vector<short int> >&)':
Main.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < set.size(); i++)
      |                     ~~^~~~~~~~~~~~
Main.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0; i < set.size(); i++)
      |                     ~~^~~~~~~~~~~~
Main.cpp:37:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (int j = i + 1; j < set.size(); j++) {
      |                             ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 433 ms 312 KB Output is correct
8 Correct 668 ms 312 KB Output is correct
9 Correct 524 ms 312 KB Output is correct
10 Correct 630 ms 308 KB Output is correct
11 Correct 302 ms 308 KB Output is correct
12 Correct 599 ms 320 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 433 ms 312 KB Output is correct
8 Correct 668 ms 312 KB Output is correct
9 Correct 524 ms 312 KB Output is correct
10 Correct 630 ms 308 KB Output is correct
11 Correct 302 ms 308 KB Output is correct
12 Correct 599 ms 320 KB Output is correct
13 Execution timed out 4053 ms 212 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 433 ms 312 KB Output is correct
8 Correct 668 ms 312 KB Output is correct
9 Correct 524 ms 312 KB Output is correct
10 Correct 630 ms 308 KB Output is correct
11 Correct 302 ms 308 KB Output is correct
12 Correct 599 ms 320 KB Output is correct
13 Execution timed out 4053 ms 212 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 433 ms 312 KB Output is correct
8 Correct 668 ms 312 KB Output is correct
9 Correct 524 ms 312 KB Output is correct
10 Correct 630 ms 308 KB Output is correct
11 Correct 302 ms 308 KB Output is correct
12 Correct 599 ms 320 KB Output is correct
13 Execution timed out 4053 ms 212 KB Time limit exceeded
14 Halted 0 ms 0 KB -