| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 687398 |
2023-01-26T11:32:01 Z |
QwertyPi |
Present (RMI21_present) |
C++14 |
|
4000 ms |
13128 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;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4035 ms |
13128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4035 ms |
13128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4035 ms |
13128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4035 ms |
13128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4035 ms |
13128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
