| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 1066799 |
2024-08-20T07:22:28 Z |
정민찬(#11123) |
Present (RMI21_present) |
C++17 |
|
3999 ms |
860 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
vector<pair<vector<int>,int>> save = {
{{},1},{{1},1},{{2},2},{{3},3},{{4},6},{{5},9},{{6},16},{{7},29},{{8},54},{{9},87},{{10},138},{{11},317},{{12},404},{{13},1017},{{14},1566},{{15},1971},{{16},4566},{{17},10041},{{18},13732},{{19},33713},{{20},39246},{{21},60383},{{22},149342},{{23},315905},{{24},356036},{{25},684169},{{26},1570362},{{27},2259607},{{28},3529378},{{29},9028225},{{30},8816192},{{31},1},{{31,1},1},{{31,2},1},{{31,3},2},{{31,4},4},{{31,5},8},{{31,6},12},{{31,7},28},{{31,8},48},{{31,9},84},{{31,10},128},{{31,11},316},{{31,12},384},{{31,13},1016},{{31,14},1536},{{31,15},1960},{{31,16},4512},{{31,17},10040},{{31,18},13632},{{31,19},33712},{{31,20},39104},{{31,21},60352},{{31,22},149024},{{31,23},315904},{{31,24},355584},{{31,25},684160},{{31,26},1569344},{{31,27},2259520},{{31,28},3527808},{{31,29},9028224},{{31,30},8814080},{{32},1},{{32,1},1},{{32,2},2},{{32,3},2},{{32,4},6},{{32,5},8},{{32,6},10},{{32,7},24},{{32,8},54},{{32,9},80},{{32,10},120},{{32,11},288},{{32,12},250},{{32,13},816},{{32,14},1304},{{32,15},1600},{{32,16},4566},{{32,17},9024},{{32,18},12624},{{32,19},30592},{{32,20},33784},{{32,21},53376},{{32,22},135840},{{32,23},283776},{{32,24},218874},{{32,25},544256},{{32,26},1269040},{{32,27},1803264},{{32,28},2933656},{{32,29},7334272},{{32,30},7161920},{{32,31,1},1},{{32,31,2},1},{{32,31,3},2},{{32,31,4},4},{{32,31,5},8},{{32,31,6},8},{{32,31,7},24},{{32,31,8},48},{{32,31,9},80},{{32,31,10},112},{{32,31,11},288},{{32,31,12},240},{{32,31,13},816},{{32,31,14},1280},{{32,31,15},1600},{{32,31,16},4512},{{32,31,17},9024},{{32,31,18},12544},{{32,31,19},30592},{{32,31,20},33664},{{32,31,21},53376},{{32,31,22},135552},{{32,31,23},283776},{{32,31,24},218624},{{32,31,25},544256},{{32,31,26},1268224},{{32,31,27},1803264},{{32,31,28},2932352},{{32,31,29},7334272},{{32,31,30},7160320},{{33},1},{{33,1},1},{{33,2},1},{{33,3},3},{{33,4},4},{{33,5},8},{{33,6},7},{{33,7},22},{{33,8},40},{{33,9},54},{{33,10},92},{{33,11},229},{{33,12},260},{{33,13},712},{{33,14},1072},{{33,15},1688},{{33,16},3392},{{33,17},7568},{{33,18},9804},{{33,19},24928},{{33,20},28160},{{33,21},56892},{{33,22},60305},{{33,23},195184},{{33,24},232688},{{33,25},435552},{{33,26},975488},{{33,27},1608212},{{33,28},2295168},{{33,29},5937344},{{33,30},5993472},{{33,31,1},1},{{33,31,2},1},{{33,31,3},2},{{33,31,4},4},{{33,31,5},8},{{33,31,6},6},{{33,31,7},22},{{33,31,8},40},{{33,31,9},52},{{33,31,10},92},{{33,31,11},228},{{33,31,12},256},{{33,31,13},712},{{33,31,14},1072},{{33,31,15},1680},{{33,31,16},3392},{{33,31,17},7568},{{33,31,18},9792},{{33,31,19},24928},{{33,31,20},28160},{{33,31,21},56864},{{33,31,22},60304},{{33,31,23},195184},{{33,31,24},232640},{{33,31,25},435552},{{33,31,26},975488},{{33,31,27},1608128},{{33,31,28},2295168},{{33,31,29},5937344},{{33,31,30},5993344},{{33,32,1},1},{{33,32,2},1},{{33,32,3},2},{{33,32,4},4},{{33,32,5},8},{{33,32,6},4},{{33,32,7},20},{{33,32,8},40},{{33,32,9},48},{{33,32,10},80},{{33,32,11},208},{{33,32,12},160},{{33,32,13},576},{{33,32,14},896},{{33,32,15},1344},{{33,32,16},3392},{{33,32,17},6784},{{33,32,18},8960},{{33,32,19},22528},{{33,32,20},24320},{{33,32,21},50304},{{33,32,22},54848},{{33,32,23},174528},{{33,32,24},142272},{{33,32,25},343232},{{33,32,26},784128},{{33,32,27},1267968},{{33,32,28},1901824},{{33,32,29},4788480},{{33,32,30},4851072},{{33,32,31,1},1},{{33,32,31,2},1},{{33,32,31,3},2},{{33,32,31,4},4},{{33,32,31,5},8},{{33,32,31,6},4},{{33,32,31,7},20},{{33,32,31,8},40},{{33,32,31,9},48},{{33,32,31,10},80},{{33,32,31,11},208},{{33,32,31,12},160},{{33,32,31,13},576},{{33,32,31,14},896},{{33,32,31,15},1344},{{33,32,31,16},3392},{{33,32,31,17},6784},{{33,32,31,18},8960},{{33,32,31,19},22528},{{33,32,31,20},24320},{{33,32,31,21},50304},{{33,32,31,22},54848},{{33,32,31,23},174528},{{33,32,31,24},142272},{{33,32,31,25},343232},{{33,32,31,26},784128},{{33,32,31,27},1267968},{{33,32,31,28},1901824},{{33,32,31,29},4788480},{{33,32,31,30},4851072},{{34},1},{{34,1},1},{{34,2},2},{{34,3},2},{{34,4},3},{{34,5},6},{{34,6},10},{{34,7},20},{{34,8},36},{{34,9},56},{{34,10},120},{{34,11},240},{{34,12},300},{{34,13},768},{{34,14},1500},{{34,15},1584},{{34,16},3952},{{34,17},8497},{{34,18},13204},{{34,19},30112},{{34,20},36096},{{34,21},52832},{{34,22},148572},{{34,23},297280},{{34,24},334464},{{34,25},640704},{{34,26},1567608},{{34,27},2173696},{{34,28},3442944},{{34,29},8751040},{{34,30},8751528},{{34,31,1},1},{{34,31,2},1},{{34,31,3},2},{{34,31,4},2},{{34,31,5},6},{{34,31,6},8},{{34,31,7},20},{{34,31,8},32},{{34,31,9},56},{{34,31,10},112},{{34,31,11},240},{{34,31,12},288},{{34,31,13},768},{{34,31,14},1472},{{34,31,15},1584},{{34,31,16},3904},{{34,31,17},8496},{{34,31,18},13120},{{34,31,19},30112},{{34,31,20},35968},{{34,31,21},52832},{{34,31,22},148256},{{34,31,23},297280},{{34,31,24},334080},{{34,31,25},640704},{{34,31,26},1566592},{{34,31,27},2173696},{{34,31,28},3441408},{{34,31,29},8751040},{{34,31,30},8749568},{{34,32,2},2},{{34,32,3},1},{{34,32,4},3},{{34,32,5},4},{{34,32,6},10},{{34,32,7},16},{{34,32,8},36},{{34,32,9},48},{{34,32,10},120},{{34,32,11},224},{{34,32,12},200},{{34,32,13},640},{{34,32,14},1304},{{34,32,15},1344},{{34,32,16},3952},{{34,32,17},7808},{{34,32,18},12624},{{34,32,19},28160},{{34,32,20},31344},{{34,32,21},48000},{{34,32,22},135840},{{34,32,23},271104},{{34,32,24},208368},{{34,32,25},517888},{{34,32,26},1269040},{{34,32,27},1750016},{{34,32,28},2865408},{{34,32,29},7150592},{{34,32,30},7161920},{{34,32,31,2},1},{{34,32,31,3},1},{{34,32,31,4},2},{{34,32,31,5},4},{{34,32,31,6},8},{{34,32,31,7},16},{{34,32,31,8},32},{{34,32,31,9},48},{{34,32,31,10},112},{{34,32,31,11},224},{{34,32,31,12},192},{{34,32,31,13},640},{{34,32,31,14},1280},{{34,32,31,15},1344},{{34,32,31,16},3904},{{34,32,31,17},7808},{{34,32,31,18},12544},{{34,32,31,19},28160},{{34,32,31,20},31232},{{34,32,31,21},48000},{{34,32,31,22},135552},{{34,32,31,23},271104},{{34,32,31,24},208128},{{34,32,31,25},517888},{{34,32,31,26},1268224},{{34,32,31,27},1750016},{{34,32,31,28},2864128},{{34,32,31,29},7150592},{{34,32,31,30},7160320},{{34,33,1},1},{{34,33,2},1},{{34,33,3},2},{{34,33,4},2},{{34,33,5},6},{{34,33,6},4},{{34,33,7},16},{{34,33,8},24},{{34,33,9},36},{{34,33,10},80},{{34,33,11},172},{{34,33,12},192},{{34,33,13},536},{{34,33,14},1024},{{34,33,15},1376},{{34,33,16},2944},{{34,33,17},6416},{{34,33,18},9408},{{34,33,19},22240},{{34,33,20},25856},{{34,33,21},50272},{{34,33,22},60016},{{34,33,23},180624},{{34,33,24},213696},{{34,33,25},400544},{{34,33,26},973440},{{34,33,27},1531264},{{34,33,28},2222976},{{34,33,29},5703168},{{34,33,30},5933952},{{34,33,31,1},1},{{34,33,31,2},1},{{34,33,31,3},2},{{34,33,31,4},2},{{34,33,31,5},6},{{34,33,31,6},4},{{34,33,31,7},16},{{34,33,31,8},24},{{34,33,31,9},36},{{34,33,31,10},80},{{34,33,31,11},172},{{34,33,31,12},192},{{34,33,31,13},536},{{34,33,31,14},1024},{{34,33,31,15},1376},{{34,33,31,16},2944},{{34,33,31,17},6416},{{34,33,31,18},9408},{{34,33,31,19},22240},{{34,33,31,20},25856},{{34,33,31,21},50272},{{34,33,31,22},60016},{{34,33,31,23},180624},{{34,33,31,24},213696},{{34,33,31,25},400544},{{34,33,31,26},973440},{{34,33,31,27},1531264},{{34,33,31,28},2222976},{{34,33,31,29},5703168},{{34,33,31,30},5933952},{{34,33,32,2},1},{{34,33,32,3},1},{{34,33,32,4},2},{{34,33,32,5},4},{{34,33,32,6},4},{{34,33,32,7},12},{{34,33,32,8},24},{{34,33,32,9},32},{{34,33,32,10},80},{{34,33,32,11},160},{{34,33,32,12},128},{{34,33,32,13},448},{{34,33,32,14},896},{{34,33,32,15},1152},{{34,33,32,16},2944},{{34,33,32,17},5888},{{34,33,32,18},8960},{{34,33,32,19},20736},{{34,33,32,20},22528},{{34,33,32,21},45696},{{34,33,32,22},54848},{{34,33,32,23},164544},{{34,33,32,24},133056},{{34,33,32,25},321984},{{34,33,32,26},784128},{{34,33,32,27},1220352},{{34,33,32,28},1844736},{{34,33,32,29},4633344},{{34,33,32,30},4851072},{{34,33,32,31,2},1},{{34,33,32,31,3},1},{{34,33,32,31,4},2},{{34,33,32,31,5},4},{{34,33,32,31,6},4},{{34,33,32,31,7},12},{{34,33,32,31,8},24},{{34,33,32,31,9},32},{{34,33,32,31,10},80},{{34,33,32,31,11},160},{{34,33,32,31,12},128},{{34,33,32,31,13},448},{{34,33,32,31,14},896},{{34,33,32,31,15},1152},{{34,33,32,31,16},2944},{{34,33,32,31,17},5888},{{34,33,32,31,18},8960},{{34,33,32,31,19},20736},{{34,33,32,31,20},22528},{{34,33,32,31,21},45696},{{34,33,32,31,22},54848},{{34,33,32,31,23},164544},{{34,33,32,31,24},133056},{{34,33,32,31,25},321984},{{34,33,32,31,26},784128},{{34,33,32,31,27},1220352},{{34,33,32,31,28},1844736},{{34,33,32,31,29},4633344},{{34,33,32,31,30},4851072},{{35},1},{{35,1},1},{{35,2},1},{{35,3},2},{{35,4},4},{{35,5},9},{{35,6},12},{{35,7},29},{{35,8},48},{{35,9},84},{{35,10},65},{{35,11},252},{{35,12},312},{{35,13},816},{{35,14},585},{{35,15},982},{{35,16},2592},{{35,17},5788},{{35,18},7544},{{35,19},19120},{{35,20},18788},{{35,21},27250},{{35,22},74000},{{35,23},158272},{{35,24},178816},{{35,25},417608},{{35,26},854112},{{35,27},1237152},{{35,28},1733892},{{35,29},4738112},{{35,30},4512268},{{35,31,1},1},{{35,31,2},1},{{35,31,3},2},{{35,31,4},4},{{35,31,5},8},{{35,31,6},12},{{35,31,7},28},{{35,31,8},48},{{35,31,9},84},{{35,31,10},64},{{35,31,11},252},{{35,31,12},312},{{35,31,13},816},{{35,31,14},584},{{35,31,15},980},{{35,31,16},2592},{{35,31,17},5788},{{35,31,18},7544},{{35,31,19},19120},{{35,31,20},18784},{{35,31,21},27248},{{35,31,22},74000},{{35,31,23},158272},{{35,31,24},178816},{{35,31,25},417600},{{35,31,26},854112},{{35,31,27},1237152},{{35,31,28},1733888},{{35,31,29},4738112},{{35,31,30},4512256},{{35,32,1},1},{{35,32,2},1},{{35,32,3},2},{{35,32,4},4},{{35,32,5},8},{{35,32,6},8},{{35,32,7},24},{{35,32,8},48},{{35,32,9},80},{{35,32,10},56},{{35,32,11},232},{{35,32,12},192},{{35,32,13},656},{{35,32,14},480},{{35,32,15},800},{{35,32,16},2592},{{35,32,17},5184},{{35,32,18},6816},{{35,32,19},17184},{{35,32,20},16128},{{35,32,21},24256},{{35,32,22},67392},{{35,32,23},142144},{{35,32,24},109312},{{35,32,25},332544},{{35,32,26},690048},{{35,32,27},987264},{{35,32,28},1441664},{{35,32,29},3845120},{{35,32,30},3665920},{{35,32,31,1},1},{{35,32,31,2},1},{{35,32,31,3},2},{{35,32,31,4},4},{{35,32,31,5},8},{{35,32,31,6},8},{{35,32,31,7},24},{{35,32,31,8},48},{{35,32,31,9},80},{{35,32,31,10},56},{{35,32,31,11},232},{{35,32,31,12},192},{{35,32,31,13},656},{{35,32,31,14},480},{{35,32,31,15},800},{{35,32,31,16},2592},{{35,32,31,17},5184},{{35,32,31,18},6816},{{35,32,31,19},17184},{{35,32,31,20},16128},{{35,32,31,21},24256},{{35,32,31,22},67392},{{35,32,31,23},142144},{{35,32,31,24},109312},{{35,32,31,25},332544},{{35,32,31,26},690048},{{35,32,31,27},987264},{{35,32,31,28},1441664},{{35,32,31,29},3845120},{{35,32,31,30},3665920},{{35,33,1},1},{{35,33,2},1},{{35,33,3},2},{{35,33,4},4},{{35,33,5},8},{{35,33,6},6},{{35,33,7},22},{{35,33,8},40},{{35,33,9},52},{{35,33,10},46},{{35,33,11},182},{{35,33,12},208},{{35,33,13},572},{{35,33,14},408},{{35,33,15},840},{{35,33,16},1936},{{35,33,17},4328},{{35,33,18},5328},{{35,33,19},13984},{{35,33,20},14240},{{35,33,21},25760},{{35,33,22},30032},{{35,33,23},98000},{{35,33,24},116928},{{35,33,25},267872},{{35,33,26},534432},{{35,33,27},882016},{{35,33,28},1175552},{{35,33,29},3172800},{{35,33,30},3111168},{{35,33,31},9456768},{{35,33,32,1},1},{{35,33,32,2},1},{{35,33,32,3},2},{{35,33,32,4},4},{{35,33,32,5},8},{{35,33,32,6},4},{{35,33,32,7},20},{{35,33,32,8},40},{{35,33,32,9},48},{{35,33,32,10},40},{{35,33,32,11},168},{{35,33,32,12},128},{{35,33,32,13},464},{{35,33,32,14},336},{{35,33,32,15},672},{{35,33,32,16},1936},{{35,33,32,17},3872},{{35,33,32,18},4800},{{35,33,32,19},12544},{{35,33,32,20},12288},{{35,33,32,21},22912},{{35,33,32,22},27328},{{35,33,32,23},87616},{{35,33,32,24},71232},{{35,33,32,25},211584},{{35,33,32,26},429504},{{35,33,32,27},695616},{{35,33,32,28},975232},{{35,33,32,29},2558400},{{35,33,32,30},2519040},{{35,33,32,31},7635840},{{35,34,1},1},{{35,34,2},1},{{35,34,3},2},{{35,34,4},2},{{35,34,5},6},{{35,34,6},8},{{35,34,7},20},{{35,34,8},32},{{35,34,9},56},{{35,34,10},56},{{35,34,11},184},{{35,34,12},216},{{35,34,13},584},{{35,34,14},552},{{35,34,15},792},{{35,34,16},2112},{{35,34,17},4624},{{35,34,18},7128},{{35,34,19},16376},{{35,34,20},16800},{{35,34,21},24448},{{35,34,22},73520},{{35,34,23},147520},{{35,34,24},166272},{{35,34,25},392800},{{35,34,26},852544},{{35,34,27},1188544},{{35,34,28},1692672},{{35,34,29},4587872},{{35,34,30},4477952},{{35,34,31,1},1},{{35,34,31,2},1},{{35,34,31,3},2},{{35,34,31,4},2},{{35,34,31,5},6},{{35,34,31,6},8},{{35,34,31,7},20},{{35,34,31,8},32},{{35,34,31,9},56},{{35,34,31,10},56},{{35,34,31,11},184},{{35,34,31,12},216},{{35,34,31,13},584},{{35,34,31,14},552},{{35,34,31,15},792},{{35,34,31,16},2112},{{35,34,31,17},4624},{{35,34,31,18},7128},{{35,34,31,19},16376},{{35,34,31,20},16800},{{35,34,31,21},24448},{{35,34,31,22},73520},{{35,34,31,23},147520},{{35,34,31,24},166272},{{35,34,31,25},392800},{{35,34,31,26},852544},{{35,34,31,27},1188544},{{35,34,31,28},1692672},{{35,34,31,29},4587872},{{35,34,31,30},4477952},{{35,34,32,2},1},{{35,34,32,3},1},{{35,34,32,4},2},{{35,34,32,5},4},{{35,34,32,6},8},{{35,34,32,7},16},{{35,34,32,8},32},{{35,34,32,9},48},{{35,34,32,10},56},{{35,34,32,11},168},{{35,34,32,12},144},{{35,34,32,13},480},{{35,34,32,14},480},{{35,34,32,15},672},{{35,34,32,16},2112},{{35,34,32,17},4224},{{35,34,32,18},6816},{{35,34,32,19},15264},{{35,34,32,20},14592},{{35,34,32,21},22272},{{35,34,32,22},67392},{{35,34,32,23},134784},{{35,34,32,24},103296},{{35,34,32,25},317184},{{35,34,32,26},690048},{{35,34,32,27},956672},{{35,34,32,28},1409024},{{35,34,32,29},3745792},{{35,34,32,30},3665920},{{35,34,32,31,2},1},{{35,34,32,31,3},1},{{35,34,32,31,4},2},{{35,34,32,31,5},4},{{35,34,32,31,6},8},{{35,34,32,31,7},16},{{35,34,32,31,8},32},{{35,34,32,31,9},48},{{35,34,32,31,10},56},{{35,34,32,31,11},168},{{35,34,32,31,12},144},{{35,34,32,31,13},480},{{35,34,32,31,14},480},{{35,34,32,31,15},672},{{35,34,32,31,16},2112},{{35,34,32,31,17},4224},{{35,34,32,31,18},6816},{{35,34,32,31,19},15264},{{35,34,32,31,20},14592},{{35,34,32,31,21},22272},{{35,34,32,31,22},67392},{{35,34,32,31,23},134784},{{35,34,32,31,24},103296},{{35,34,32,31,25},317184},{{35,34,32,31,26},690048},{{35,34,32,31,27},956672},{{35,34,32,31,28},1409024},{{35,34,32,31,29},3745792},{{35,34,32,31,30},3665920},{{35,34,33,1},1},{{35,34,33,2},1},{{35,34,33,3},2},{{35,34,33,4},2},{{35,34,33,5},6},{{35,34,33,6},4},{{35,34,33,7},16},{{35,34,33,8},24},{{35,34,33,9},36},{{35,34,33,10},40},{{35,34,33,11},132},{{35,34,33,12},144},{{35,34,33,13},408},{{35,34,33,14},384},{{35,34,33,15},688},{{35,34,33,16},1584},{{35,34,33,17},3472},{{35,34,33,18},5040},{{35,34,33,19},11984},{{35,34,33,20},12768},{{35,34,33,21},23328},{{35,34,33,22},29856},{{35,34,33,23},89920},{{35,34,33,24},106560},{{35,34,33,25},248032},{{35,34,33,26},533280},{{35,34,33,27},839520},{{35,34,33,28},1139904},{{35,34,33,29},3047136},{{35,34,33,30},3080448},{{35,34,33,31},9174720},{{35,34,33,32,2},1},{{35,34,33,32,3},1},{{35,34,33,32,4},2},{{35,34,33,32,5},4},{{35,34,33,32,6},4},{{35,34,33,32,7},12},{{35,34,33,32,8},24},{{35,34,33,32,9},32},{{35,34,33,32,10},40},{{35,34,33,32,11},120},{{35,34,33,32,12},96},{{35,34,33,32,13},336},{{35,34,33,32,14},336},{{35,34,33,32,15},576},{{35,34,33,32,16},1584},{{35,34,33,32,17},3168},{{35,34,33,32,18},4800},{{35,34,33,32,19},11136},{{35,34,33,32,20},11136},{{35,34,33,32,21},21248},{{35,34,33,32,22},27328},{{35,34,33,32,23},81984},{{35,34,33,32,24},66240},{{35,34,33,32,25},199296},{{35,34,33,32,26},429504},{{35,34,33,32,27},669120},{{35,34,33,32,28},946944},{{35,34,33,32,29},2475072},{{35,34,33,32,30},2519040},{{35,34,33,32,31},7469184},{{36},1},{{36,1},1},{{36,2},2},{{36,3},3},{{36,4},6},{{36,5},8},{{36,6},16},{{36,7},28},{{36,8},27},{{36,9},67},{{36,10},90},{{36,11},228},{{36,12},404},{{36,13},840},{{36,14},1272},{{36,15},1416},{{36,16},2820},{{36,17},7120},{{36,18},9868},{{36,19},24032},{{36,20},33144},{{36,21},45052},{{36,22},113500},{{36,23},239360},{{36,24},154953},{{36,25},436160},{{36,26},1008800},{{36,27},925482},{{36,28},2275958},{{36,29},5277952},{{36,30},1302430},{{36,31},0},{{36,32},0},{{36,33},0},{{36,34},0},{{36,35},0},{{37},0},{{38},0},{{39},0},{{40},0},{{41},0},{{42},0},{{43},0},{{44},0},{{45},0},{{46},0},{{47},0},{{48},0},{{49},0},{{50},0},{{51},0},{{52},0},{{53},0},{{54},0},{{55},0},{{56},0},{{57},0},{{58},0},{{59},0},{{60},0},{{61},0},{{62},0},{{63},0},{{64},0},{{65},0},{{66},0},{{67},0},{{68},0},{{69},0},{{70},0},{{71},0},{{72},0},{{73},0},{{74},0},{{75},0},{{76},0},{{77},0},{{78},0},{{79},0},{{80},0},{{81},0},{{82},0},{{83},0},{{84},0},{{85},0},{{86},0},{{87},0},{{88},0},{{89},0},{{90},0},{{91},0},{{92},0},{{93},0},{{94},0},{{95},0},{{96},0},{{97},0},{{98},0},{{99},0},{{100},0}};
vector<int> v;
int G[101][101];
int chk[101];
int cnt;
bool flag;
void go(int p) {
if (flag) return;
int lo = 0;
for (int i=p-1; i>=1; i--) {
if (chk[i]) {
lo = i;
break;
}
}
if (!lo) {
cnt --;
if (cnt == 0) {
cout << v.size() << ' ';
for (int i=v.size()-1; i>=0; i--) {
cout << v[i] << ' ';
}
cout << '\n';
flag = true;
return;
}
}
lo = max(1, lo);
for (int i=lo; i<p; i++) {
for (auto &j : v) {
chk[G[i][j]] ++;
}
v.push_back(i);
go(i);
v.pop_back();
for (auto &j : v) {
chk[G[i][j]] --;
}
}
}
int main() {
ios_base :: sync_with_stdio(false); cin.tie(NULL);
for (int i=1; i<=100; i++) {
for (int j=1; j<=100; j++) {
G[i][j] = __gcd(i, j);
}
}
vector<int> S(save.size());
S[0] = save[0].second;
for (int i=1; i<save.size(); i++) {
S[i] = S[i-1] + save[i].second;
}
int T;
cin >> T;
while (T --) {
int x;
cin >> x;
if (x == 0) {
cout << "0\n";
continue;
}
x ++;
int idx = lower_bound(S.begin(), S.end(), x) - S.begin();
v = save[idx].first;
cnt = x;
cnt -= S[idx-1];
memset(chk, 0, sizeof(chk));
for (int i=0; i<v.size(); i++) {
for (int j=i+1; j<v.size(); j++) {
chk[G[v[i]][v[j]]] ++;
}
}
flag = false;
go(v.back());
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::vector<int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (int i=1; i<save.size(); i++) {
| ~^~~~~~~~~~~~
Main.cpp:80:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int i=0; i<v.size(); i++) {
| ~^~~~~~~~~
Main.cpp:81:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (int j=i+1; j<v.size(); j++) {
| ~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
676 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
676 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
88 ms |
604 KB |
Output is correct |
| 8 |
Correct |
80 ms |
604 KB |
Output is correct |
| 9 |
Correct |
49 ms |
604 KB |
Output is correct |
| 10 |
Correct |
119 ms |
604 KB |
Output is correct |
| 11 |
Correct |
34 ms |
604 KB |
Output is correct |
| 12 |
Correct |
63 ms |
604 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
676 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
88 ms |
604 KB |
Output is correct |
| 8 |
Correct |
80 ms |
604 KB |
Output is correct |
| 9 |
Correct |
49 ms |
604 KB |
Output is correct |
| 10 |
Correct |
119 ms |
604 KB |
Output is correct |
| 11 |
Correct |
34 ms |
604 KB |
Output is correct |
| 12 |
Correct |
63 ms |
604 KB |
Output is correct |
| 13 |
Correct |
669 ms |
604 KB |
Output is correct |
| 14 |
Correct |
1097 ms |
600 KB |
Output is correct |
| 15 |
Correct |
2070 ms |
652 KB |
Output is correct |
| 16 |
Correct |
3999 ms |
652 KB |
Output is correct |
| 17 |
Correct |
574 ms |
656 KB |
Output is correct |
| 18 |
Correct |
1457 ms |
848 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
676 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
88 ms |
604 KB |
Output is correct |
| 8 |
Correct |
80 ms |
604 KB |
Output is correct |
| 9 |
Correct |
49 ms |
604 KB |
Output is correct |
| 10 |
Correct |
119 ms |
604 KB |
Output is correct |
| 11 |
Correct |
34 ms |
604 KB |
Output is correct |
| 12 |
Correct |
63 ms |
604 KB |
Output is correct |
| 13 |
Correct |
669 ms |
604 KB |
Output is correct |
| 14 |
Correct |
1097 ms |
600 KB |
Output is correct |
| 15 |
Correct |
2070 ms |
652 KB |
Output is correct |
| 16 |
Correct |
3999 ms |
652 KB |
Output is correct |
| 17 |
Correct |
574 ms |
656 KB |
Output is correct |
| 18 |
Correct |
1457 ms |
848 KB |
Output is correct |
| 19 |
Runtime error |
1 ms |
860 KB |
Execution killed with signal 11 |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
676 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
88 ms |
604 KB |
Output is correct |
| 8 |
Correct |
80 ms |
604 KB |
Output is correct |
| 9 |
Correct |
49 ms |
604 KB |
Output is correct |
| 10 |
Correct |
119 ms |
604 KB |
Output is correct |
| 11 |
Correct |
34 ms |
604 KB |
Output is correct |
| 12 |
Correct |
63 ms |
604 KB |
Output is correct |
| 13 |
Correct |
669 ms |
604 KB |
Output is correct |
| 14 |
Correct |
1097 ms |
600 KB |
Output is correct |
| 15 |
Correct |
2070 ms |
652 KB |
Output is correct |
| 16 |
Correct |
3999 ms |
652 KB |
Output is correct |
| 17 |
Correct |
574 ms |
656 KB |
Output is correct |
| 18 |
Correct |
1457 ms |
848 KB |
Output is correct |
| 19 |
Runtime error |
1 ms |
860 KB |
Execution killed with signal 11 |
| 20 |
Halted |
0 ms |
0 KB |
- |
