제출 #687359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
687359		QwertyPi	Present (RMI21_present)	C++14	29 / 100	4035 ms	340 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;
 
int g[65][65];
int B = 1;

bool ok(uint64_t b){
    for(uint64_t i = b; i; i -= i & -i){
        for(uint64_t j = i; j; j -= j & -j){
            uint64_t x = i & -i, y = j & -j;
            if(!(b & (1ULL << g[__builtin_clzll(x)][__builtin_clzll(y)]))) return false;
        }
    }
    return true;
}
 
void out(uint64_t b){
    vector<int> v;
    for(int i = 0; i < 64; i++){
        if(b & (1ULL << i)) v.push_back(i + 1);
    }
    cout << v.size() << ' ';
    for(auto i : v) cout << i << ' ';
    cout << endl;
}

const int ST = 5e5;
uint64_t a[6001] = {0, 6415551, 16875563, 27398715, 37996375, 47466703, 58218911, 71702511, 85307503, 102168543, 115369951, 133960639, 145427647, 163659647, 177042815, 195509247, 216122559, 239768959, 265554303, 274333407, 284435415, 294690527, 306146687, 315099055, 325960347, 339810053, 352927583, 369956363, 382573487, 400829151, 413083375, 430289115, 444714719, 462230715, 482943919, 507589687, 531634543, 549603639, 572835271, 591206111, 616833207, 647032575, 678626151, 711878335, 752552943, 805651231, 822161563, 843482731, 863457079, 891401143, 921961143, 954081007, 986877423, 1030753663, 1075004959, 1081891135, 1092852607, 1105360703, 1113627215, 1124345895, 1136479039, 1147864327, 1162610431, 1178677551, 1193154399, 1210258439, 1223833215, 1242246975, 1256156415, 1275608991, 1295885951, 1318396767, 1343045023, 1349767503, 1360744639, 1372723239, 1381436783, 1392250783, 1403603775, 1415848495, 1430406463, 1446351887, 1460534079, 1477976287, 1491402959, 1510266687, 1523149631, 1543530911, 1562765119, 1585478047, 1611914303, 1628776287, 1649817455, 1671615167, 1698972831, 1729577279, 1761883295, 1795240223, 1842813439, 1882658863, 1901206079, 1920994935, 1946481871, 1974952319, 2003982143, 2036655551, 2070011519, 2118481055, 2150901447, 2162578879, 2176517631, 2187445535, 2201334879, 2217529215, 2234282879, 2252930943, 2271519199, 2288950847, 2311617791, 2328804095, 2351859151, 2381624831, 2406329471, 2421732607, 2435126231, 2450469759, 2459301631, 2473415167, 2489588799, 2508047487, 2525897215, 2550304127, 2565647071, 2586302079, 2604318975, 2626520767, 2655912223, 2686501087, 2708542783, 2734727487, 2765834239, 2804160063, 2843599615, 2888099135, 2952562687, 2973086335, 2997065455, 3026760255, 3065024959, 3105941151, 3146055935, 3206650111, 3227129983, 3240473711, 3255846975, 3264840895, 3278828671, 3294933183, 3313567167, 3331425695, 3355677279, 3371116031, 3391663775, 3409895679, 3432176127, 3461385343, 3490534749, 3498415007, 3512710399, 3526894463, 3540038895, 3555702463, 3569993471, 3591398015, 3608216127, 3627815423, 3645338751, 3664056351, 3685690367, 3711275135, 3739951615, 3764683919, 3793916223, 3816256767, 3855889919, 3893864703, 3931024255, 3980723327, 4030969519, 4060193567, 4081131839, 4114966079, 4153263103, 4196393983, 4237406719, 4296171263, 4309730503, 4328880199, 4342780815, 4363019743, 4380394855, 4401418143, 4425291175, 4448075679, 4474012751, 4502914087, 4535825871, 4565910567, 4580588719, 4598386855, 4614042983, 4633060647, 4651819319, 4672504999, 4697763879, 4719499711, 4746253487, 4775073023, 4807990479, 4840298551, 4872027431, 4906571735, 4947543783, 5000444591};
int main(){
    for(int i = 1; i <= 64; i++) for(int j = 1; j <= 64; j++) g[63 - (i - 1)][63 - (j - 1)] = __gcd(i, j) - 1;
    int cnt = 0;
    /*
    for(uint64_t i = 0;; i++){
        while(i >= (1ULL << B)) B++;
        if(ok(i)) { if(cnt % ST == 0) cout << i << ", "; cnt++; }
        if(cnt >= 1500000000) break;
    }
    */
    int L; cin >> L;
    for(int i = 0; i < L; i++){
        int x, y = 0; cin >> x;
        B = 0;
        y = a[x / ST], x %= ST;
        for(; ; y++){
            while(y >= (1ULL << B)) B++;
            if(ok(y)) { if(x == 0) { out(y); break; } x--; }
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   47 |             while(y >= (1ULL << B)) B++;
      |                   ~~^~~~~~~~~~~~~~
Main.cpp:33:9: warning: unused variable 'cnt' [-Wunused-variable]
   33 |     int cnt = 0;
      |         ^~~

• Subtask 1: 8 / 8
• Subtask 2: 21 / 21
• Subtask 3: 0 / 41
• Subtask 4: 0 / 14
• Subtask 5: 0 / 16