oj.uz

Submission #687401

# Submission time Handle Problem Language Result Execution time Memory
687401 2023-01-26T11:33:06 Z QwertyPi Present (RMI21_present) C++14
29 / 100
 4000 ms 13148 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#define u64 uint64_t
using namespace std;

u64 dp[8][8][1 << 8][1 << 8];

bool ok(uint64_t b){
    uint64_t r = 0;
    uint64_t x[5];
    for(int i = 0; i < 5; i++){
        x[i] = (b >> 8 * i) & 0xff;
    }
    for(int i = 0; i < 5; i++){
        for(int j = i; j < 5; j++){
            r |= dp[i][j][x[i]][x[j]];
        }
    }
    return r == b;
}
 
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 = 2e6;
uint64_t a[751] = {
0, 37996375, 85307503, 145427647, 216122559, 284435415, 325960347, 382573487, 444714719, 531634543, 616833207, 752552943, 863457079, 986877423, 1092852607, 1136479039, 1193154399, 1256156415, 1343045023, 1381436783, 1430406463, 1491402959, 1562765119, 1649817455, 1761883295, 1901206079, 2003982143, 2150901447, 2201334879, 2271519199, 2351859151, 2435126231, 2489588799, 2565647071, 2655912223, 2765834239, 2952562687, 3065024959, 3227129983, 3278828671, 3355677279, 3432176127, 3512710399, 3569993471, 3645338751, 3739951615, 3855889919, 4030969519, 4153263103, 4309730503, 4380394855, 4474012751, 4580588719, 4651819319, 4746253487, 4872027431, 5057146687, 5216671591, 5387726527, 5459722143, 5555339615, 5658462999, 5731341215, 5826908319, 5954479791, 6147849583, 6304068279, 6476249263, 6572783015, 6711830847, 6796613279, 6917049629, 7085106095, 7315146927, 7528903847, 7621435687, 7752447439, 7852021095, 7959786703, 8120382823, 8355116887, 8588431039, 8629292591, 8680212179, 8743205051, 8819775359, 8881514571, 8927631967, 8988944991, 9053292927, 9142144763, 9242917871, 9397735287, 9489765751, 9634335855, 9699525083, 9745990831, 9807360367, 9880027999, 9949810111, 9993530939, 10053041271, 10117752143, 10206271727, 10303646583, 10450380143, 
10545595831, 10679454703, 10774052543, 10839528791, 10912932207, 11010688863, 11062939851, 11140829851, 11224007007, 11329204763, 11487524335, 11626710199, 11811366635, 11861541815, 11931408223, 12013288623, 12098830647, 12154097751, 12233040095, 12327536575, 12440366527, 12619992175, 12740481719, 12900706263, 12975152407, 13073922479, 13179646327, 13258270895, 13360211311, 13494250367, 13697161079, 13859001199, 13997338303, 14077726047, 14193654623, 14275454647, 14361994415, 14479238447, 14623901559, 14814472895, 15010985855, 15112391855, 15235983279, 15351175519, 15460508079, 15611412919, 15845736175, 16061328767, 16179019119, 16299279807, 16417065391, 16526725855, 16679151287, 16913806679, 17117079919, 17239426495, 17353729151, 17481255423, 17574418207, 17727659007, 17966786047, 18183321343, 18313970047, 18427977839, 18555679991, 18649014495, 18803081079, 19043190367, 19259368959, 19408459207, 19571790591, 19686110039, 19859804927, 20143816443, 20411450879, 20525201791, 20688650335, 20806829407, 20994659895, 21282666495, 21529663039, 21713000287, 21858110847, 22084147319, 22424463103, 22641135903, 22834112095, 22983247615, 23253288543, 23623542495, 23810585983, 24012477023, 24325822463, 24722030847, 24936686943, 25128967167, 25503781983, 25798117631, 25894291231, 26043036499, 26129453503, 26265852287, 26462064127, 26698138847, 26884229823, 26990681295, 27130951935, 27222868351, 27372393215, 27586270815, 27819697919, 27987906927, 28152818047, 28273854047, 28448445183, 28733081271, 29002012911, 29121139935, 29282878687, 29410670555, 29611093503, 29901385215, 30136417503, 30337652575, 30485868927, 30750435071, 31128356095, 31277636351, 31462399359, 31658087807, 31982841719, 32270675711, 32502449087, 32721365375, 33107842911, 33396214527, 33620481791, 33877627071, 34311654911, 34414927359, 34528270047, 34641678015, 34729663295, 34828515839, 35033100015, 35271350639, 35458484415, 35559249343, 35669142399, 35752469951, 35859370159, 35996002559, 36250061423, 36508114479, 36608836879, 36725809023, 36832949343, 36959526879, 37184705775, 37482497983, 37636359103, 37757743039, 37885982095, 38005463743, 38161341631, 38460493759, 38695997231, 38856951135, 39008936831, 39200348607, 39545166655, 39784875455, 39965493215, 40108105519, 40305213375, 40673959679, 40920629119, 41105364447, 41289451455, 
41692937727, 41976823679, 42165946655, 42342035391, 42730680319, 42985649855, 43088987071, 43218162911, 43283992511, 43392994271, 43552202495, 43804728623, 44037155807, 44127395647, 44229271519, 44332525535, 44443628479, 44576014079, 44833210239, 45081574911, 45189177279, 45313794015, 45423832959, 45552469343, 45786314495, 46077012415, 46233374655, 46358773503, 46480644543, 46609885119, 46798389119, 47113142143, 47307832367, 47499783519, 47648677855, 47864438271, 48237805311, 48433683327, 48606977215, 48758788063, 49037885375, 49403248607, 49580779391, 49783330751, 50064162687, 50477702367, 50654666687, 50857297855, 51138122879, 51551129343, 51726643071, 51922714111, 52230864639, 52642806655, 52838573407, 53024488319, 53388672511, 53744024159, 53990279039, 54250536447, 54782186175, 55029568831, 55229295839, 55758946047, 56104421711, 56417623807, 56971050879, 57267336575, 57776643839, 58243284479, 58689093375, 59238972927, 59627249535, 60181115775, 60405160895, 60584859263, 60992989695, 61297982975, 61508620367, 61729959807, 62186159871, 62452678527, 62697594751, 63135874815, 63490680703, 63721512831, 64106823167, 64548185983, 64851664767, 65482604031, 65785106303, 66170732287, 66723082111, 67093134847, 67748048767, 68102586111, 68725445583, 68766182059, 68821033611, 68881442623, 68958664667, 69013370839, 69058616751, 69118996055, 69180633311, 69267822187, 69364829119, 69524848693, 69609234239, 69747670847, 69823923605, 69866930279, 69929199455, 69994624531, 70068865259, 70110959319, 70165310159, 70229438895, 70303757707, 70389105907, 70512803519, 70639526375, 70754318043, 70881251247, 70936523735, 71008066795, 71098549695, 71169587163, 71226675103, 71305462891, 71405158887, 71522322391, 71691558719, 71823640091, 71959707551, 72014140391, 72089812911, 72180334495, 72246038759, 72310367535, 72383246891, 72483898611, 72612314943, 72777978807, 72914485167, 73048130279, 73120449063, 73221386191, 73317554983, 73391017319, 73493387567, 73624781927, 73827159215, 73987766191, 74124434639, 74198948783, 74303307247, 74394675175, 74470612799, 74575894751, 74709470015, 74909620199, 75070594879, 75213092767, 75318746975, 75448322007, 75540483279, 75673481167, 75864751807, 76076712935, 76270413799, 76370245535, 76506170831, 76592557983, 76713053391, 76881879527, 77111230271, 77315983067, 77359021791, 
77415102091, 77479933855, 77561402507, 77613576755, 77659800551, 77721116591, 77793615711, 77884039283, 77993303871, 78135038391, 78238073655, 78386043499, 78426437335, 78483849875, 78544812203, 78623135647, 78681407731, 78725465447, 78788897387, 78856463719, 78946499839, 79054570611, 79197329079, 79295763623, 79451684479, 79505359539, 79575666591, 79656714143, 79743491999, 79798860239, 79877016123, 79969222559, 80082457503, 80264542827, 80382911447, 80538307535, 80596117431, 80669750955, 80758496991, 80833792463, 80895696319, 80971703403, 81073035695, 81201820763, 81365676275, 81503906223, 81639089127, 81715792999, 81824436063, 81915027047, 81997993271, 82113293775, 82253606383, 82448933095, 82634098263, 82733363615, 82820707791, 82946650471, 83014834639, 83105957791, 83229753263, 83392503535, 83571533527, 83762233071, 83858269543, 83993384399, 84092598223, 84211342511, 84377263935, 84606797751, 84831303383, 84928076719, 85061194655, 85162287007, 85278868383, 85437240679, 85669978031, 85902574687, 85983857311, 86108663647, 86218618707, 86325105403, 86486738295, 86734227831, 86976704583, 87058110581, 87183610463, 87292709595, 87399395551, 87560905299, 87809077623, 88051290137, 88161458639, 88325807007, 88439481303, 88624834423, 88909388475, 89156387639, 89284017887, 89429369815, 89563392351, 89780491735, 90078215807, 90283006623, 90476056383, 90622082687, 90886517119, 91264138879, 91400980383, 91582728655, 91756406623, 92081608287, 92378838743, 92603162335, 92788763855, 93168336511, 93482931927, 93705429975, 93915840223, 94300141311, 94536631527, 94646023007, 94781294551, 94877581971, 95030909499, 95262615391, 95484894847, 95624115315, 95743457387, 95869511507, 95971825503, 96133538935, 96382548735, 96625540735, 96741708759, 96911595059, 97027340115, 97214271035, 97499029311, 97747013211, 97880746059, 98027999135, 98168471167, 98402786943, 98701194971, 98894171039, 99088241503, 99258773343, 99589763447, 99884495319, 100048314207, 100219033303, 100437659455, 100771219263, 101038117335, 101260224471, 101519201751, 101943453535, 102175030911, 102387213271, 102694420095, 103085085837, 103161945919, 103266279231, 103381247659, 103482946767, 103589486511, 103801563835, 104054655595, 104193363919, 104301621087, 104424125547, 104492134895, 104598208415, 104758499759, 105008944319, 105244732527, 105364045743, 105496019097, 105596741535, 105713775967, 105968489343, 106300449583, 106391881119, 106508887435, 106624322107, 106745839567, 106974194411, 107266243839, 107448446287, 107643222991, 107779080111, 107985952175, 108359946159, 108551608271, 108724766861, 108869123711, 109121707951, 109505314623, 109679869855, 109859614671, 110085099199, 110522203839, 110743006159, 110918672287, 111135162175, 111569239871, 111720305435, 111832013263, 111948750655, 112039760783, 112141143983, 112346835563, 112597589823, 112777004139, 112880013215, 112998183775, 113069805471, 113184015467, 113334422975, 113589105903, 113830805455, 113953333151, 114085988971, 114189136207, 114310692335, 114588393391, 114892310479, 114996127115, 115125593483, 115229255519, 115350393759, 115597546731, 115888619135, 116077473743, 116251809695, 116403365791, 116680564591, 117044905167, 117193613215, 117352946095, 117524561727, 117864546167, 118156963791, 118369243999, 118548468687, 118901210495, 119231491023, 119443369295, 119622287279, 119975902079, 120299463771, 120527947711, 120693743455, 121085654135, 121390650231, 121616611711, 121790555999, 122201061887, 122542084959, 122752888287, 123114520191, 123537905567, 123784508667, 124051002555, 124585746111, 124869983967, 125331766143, 125775845743, 126068241615, 126703282015, 127024603039, 127629917567, 128061113791, 128581345087, 128952786751, 129156607199, 129388382779, 129845280507, 130076300127, 130262663563, 130529934719, 131015245663, 131259301343, 131468670411, 132008705407};

int32_t main(){
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            for(int a = 0; a < 8; a++){
                for(int b = 0; b < 8; b++){
                    dp[i][j][1 << a][1 << b] |= 1ULL << __gcd(i * 8 + a + 1, j * 8 + b + 1) - 1;
                }
            }
            for(int x = 0; x < (1 << 8); x++){
                for(int y = 0; y < (1 << 8); y++){
                    for(int a = 0; a < 8; a++) if(x & (1 << a)) dp[i][j][x][y] |= dp[i][j][x - (1 << a)][y];
                    for(int b = 0; b < 8; b++) if(y & (1 << b)) dp[i][j][x][y] |= dp[i][j][x][y - (1 << b)];
                }
            }
        }
    }
    int cnt = 0;
    /*
    for(uint64_t i = 0;; i++){
        if(ok(i)) { if(cnt % ST == 0) cout << i << ", "; cnt++; }
        if(cnt >= 1500000000LL) break;
    }
    */
    int L; cin >> L;
    for(int i = 0; i < L; i++){
        int x, y = 0; cin >> x;
        y = a[x / ST], x %= ST;
        for(; ; y++){
            if(ok(y)) { if(x == 0) { out(y); break; } x--; }
        }
    }
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:45:93: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   45 |                     dp[i][j][1 << a][1 << b] |= 1ULL << __gcd(i * 8 + a + 1, j * 8 + b + 1) - 1;
      |                                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
Main.cpp:56:9: warning: unused variable 'cnt' [-Wunused-variable]
   56 |     int cnt = 0;
      |         ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 13056 KB Output is correct
2 Correct 59 ms 13056 KB Output is correct
3 Correct 58 ms 13048 KB Output is correct
4 Correct 56 ms 13044 KB Output is correct
5 Correct 56 ms 13076 KB Output is correct
6 Correct 61 ms 13148 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 13056 KB Output is correct
2 Correct 59 ms 13056 KB Output is correct
3 Correct 58 ms 13048 KB Output is correct
4 Correct 56 ms 13044 KB Output is correct
5 Correct 56 ms 13076 KB Output is correct
6 Correct 61 ms 13148 KB Output is correct
7 Correct 1107 ms 13148 KB Output is correct
8 Correct 1508 ms 13144 KB Output is correct
9 Correct 1124 ms 13100 KB Output is correct
10 Correct 1448 ms 13132 KB Output is correct
11 Correct 686 ms 13132 KB Output is correct
12 Correct 1371 ms 13136 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 13056 KB Output is correct
2 Correct 59 ms 13056 KB Output is correct
3 Correct 58 ms 13048 KB Output is correct
4 Correct 56 ms 13044 KB Output is correct
5 Correct 56 ms 13076 KB Output is correct
6 Correct 61 ms 13148 KB Output is correct
7 Correct 1107 ms 13148 KB Output is correct
8 Correct 1508 ms 13144 KB Output is correct
9 Correct 1124 ms 13100 KB Output is correct
10 Correct 1448 ms 13132 KB Output is correct
11 Correct 686 ms 13132 KB Output is correct
12 Correct 1371 ms 13136 KB Output is correct
13 Execution timed out 4046 ms 13088 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 13056 KB Output is correct
2 Correct 59 ms 13056 KB Output is correct
3 Correct 58 ms 13048 KB Output is correct
4 Correct 56 ms 13044 KB Output is correct
5 Correct 56 ms 13076 KB Output is correct
6 Correct 61 ms 13148 KB Output is correct
7 Correct 1107 ms 13148 KB Output is correct
8 Correct 1508 ms 13144 KB Output is correct
9 Correct 1124 ms 13100 KB Output is correct
10 Correct 1448 ms 13132 KB Output is correct
11 Correct 686 ms 13132 KB Output is correct
12 Correct 1371 ms 13136 KB Output is correct
13 Execution timed out 4046 ms 13088 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 13056 KB Output is correct
2 Correct 59 ms 13056 KB Output is correct
3 Correct 58 ms 13048 KB Output is correct
4 Correct 56 ms 13044 KB Output is correct
5 Correct 56 ms 13076 KB Output is correct
6 Correct 61 ms 13148 KB Output is correct
7 Correct 1107 ms 13148 KB Output is correct
8 Correct 1508 ms 13144 KB Output is correct
9 Correct 1124 ms 13100 KB Output is correct
10 Correct 1448 ms 13132 KB Output is correct
11 Correct 686 ms 13132 KB Output is correct
12 Correct 1371 ms 13136 KB Output is correct
13 Execution timed out 4046 ms 13088 KB Time limit exceeded
14 Halted 0 ms 0 KB -