Submission #643703

#	Time	Username	Problem	Language	Result	Execution time	Memory
643703		Matteo_Verz	Present (RMI21_present)	C++17	29 / 100	4053 ms	332 KiB

Main

#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 (stderr)

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 / 8
• Subtask 2: 21 / 21
• Subtask 3: 0 / 41
• Subtask 4: 0 / 14
• Subtask 5: 0 / 16