Submission #1066827

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1066827	2024-08-20T07:47:49 Z	정민찬(#11123)	Present (RMI21_present)	C++17	29 / 100	4000 ms	624 KB

Main

#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},26870529},{{32},43662294},{{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},17868032},{{33,32},28856064},{{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},26251648},{{34,32},42927520},{{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},17340288},{{34,33,32},28235520},{{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},13988480},{{35,32},22712320},{{35,33},34185216},{{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},13653696},{{35,34,32},22315008},{{35,34,33},33287808},{{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},4342734},{{36,31},14897408},{{36,32},25115752},{{36,33},35796672},{{36,34,2},2},{{36,34,3},1},{{36,34,4},3},{{36,34,5},4},{{36,34,6},10},{{36,34,7},16},{{36,34,8},18},{{36,34,9},36},{{36,34,10},90},{{36,34,11},168},{{36,34,12},300},{{36,34,13},624},{{36,34,14},1272},{{36,34,15},1152},{{36,34,16},2464},{{36,34,17},6080},{{36,34,18},9340},{{36,34,19},21440},{{36,34,20},30832},{{36,34,21},39648},{{36,34,22},113500},{{36,34,23},226496},{{36,34,24},145320},{{36,34,25},409984},{{36,34,26},1008800},{{36,34,27},897280},{{36,34,28},2229408},{{36,34,29},5141760},{{36,34,30},4312704},{{36,34,31},14595072},{{36,34,32},24728640},{{36,34,33},34956288},{{36,35,1},1},{{36,35,2},1},{{36,35,3},2},{{36,35,4},4},{{36,35,5},8},{{36,35,6},12},{{36,35,7},28},{{36,35,8},24},{{36,35,9},64},{{36,35,10},42},{{36,35,11},186},{{36,35,12},312},{{36,35,13},684},{{36,35,14},468},{{36,35,15},704},{{36,35,16},1608},{{36,35,17},4148},{{36,35,18},5456},{{36,35,19},13752},{{36,35,20},15616},{{36,35,21},20320},{{36,35,22},55856},{{36,35,23},119296},{{36,35,24},77376},{{36,35,25},269184},{{36,35,26},549440},{{36,35,27},507616},{{36,35,28},1110304},{{36,35,29},2752512},{{36,35,30},2211840},{{36,35,31},7716864},{{36,35,32},12974592},{{36,35,33},18982656},{{36,35,34},46409856},{{37},1},{{37,1},1},{{37,2},1},{{37,3},2},{{37,4},4},{{37,5},8},{{37,6},12},{{37,7},28},{{37,8},48},{{37,9},84},{{37,10},128},{{37,11},316},{{37,12},384},{{37,13},1016},{{37,14},1536},{{37,15},1960},{{37,16},4512},{{37,17},10040},{{37,18},13632},{{37,19},33712},{{37,20},39104},{{37,21},60352},{{37,22},149024},{{37,23},315904},{{37,24},355584},{{37,25},684160},{{37,26},1569344},{{37,27},2259520},{{37,28},3527808},{{37,29},9028224},{{37,30},8814080},{{37,31},26870528},{{37,32},43657728},{{37,33,1},1},{{37,33,2},1},{{37,33,3},2},{{37,33,4},4},{{37,33,5},8},{{37,33,6},6},{{37,33,7},22},{{37,33,8},40},{{37,33,9},52},{{37,33,10},92},{{37,33,11},228},{{37,33,12},256},{{37,33,13},712},{{37,33,14},1072},{{37,33,15},1680},{{37,33,16},3392},{{37,33,17},7568},{{37,33,18},9792},{{37,33,19},24928},{{37,33,20},28160},{{37,33,21},56864},{{37,33,22},60304},{{37,33,23},195184},{{37,33,24},232640},{{37,33,25},435552},{{37,33,26},975488},{{37,33,27},1608128},{{37,33,28},2295168},{{37,33,29},5937344},{{37,33,30},5993344},{{37,33,31},17868032},{{37,33,32},28856064},{{37,34,1},1},{{37,34,2},1},{{37,34,3},2},{{37,34,4},2},{{37,34,5},6},{{37,34,6},8},{{37,34,7},20},{{37,34,8},32},{{37,34,9},56},{{37,34,10},112},{{37,34,11},240},{{37,34,12},288},{{37,34,13},768},{{37,34,14},1472},{{37,34,15},1584},{{37,34,16},3904},{{37,34,17},8496},{{37,34,18},13120},{{37,34,19},30112},{{37,34,20},35968},{{37,34,21},52832},{{37,34,22},148256},{{37,34,23},297280},{{37,34,24},334080},{{37,34,25},640704},{{37,34,26},1566592},{{37,34,27},2173696},{{37,34,28},3441408},{{37,34,29},8751040},{{37,34,30},8749568},{{37,34,31},26251648},{{37,34,32},42923008},{{37,34,33,1},1},{{37,34,33,2},1},{{37,34,33,3},2},{{37,34,33,4},2},{{37,34,33,5},6},{{37,34,33,6},4},{{37,34,33,7},16},{{37,34,33,8},24},{{37,34,33,9},36},{{37,34,33,10},80},{{37,34,33,11},172},{{37,34,33,12},192},{{37,34,33,13},536},{{37,34,33,14},1024},{{37,34,33,15},1376},{{37,34,33,16},2944},{{37,34,33,17},6416},{{37,34,33,18},9408},{{37,34,33,19},22240},{{37,34,33,20},25856},{{37,34,33,21},50272},{{37,34,33,22},60016},{{37,34,33,23},180624},{{37,34,33,24},213696},{{37,34,33,25},400544},{{37,34,33,26},973440},{{37,34,33,27},1531264},{{37,34,33,28},2222976},{{37,34,33,29},5703168},{{37,34,33,30},5933952},{{37,34,33,31},17340288},{{37,34,33,32},28235520},{{37,35,1},1},{{37,35,2},1},{{37,35,3},2},{{37,35,4},4},{{37,35,5},8},{{37,35,6},12},{{37,35,7},28},{{37,35,8},48},{{37,35,9},84},{{37,35,10},64},{{37,35,11},252},{{37,35,12},312},{{37,35,13},816},{{37,35,14},584},{{37,35,15},980},{{37,35,16},2592},{{37,35,17},5788},{{37,35,18},7544},{{37,35,19},19120},{{37,35,20},18784},{{37,35,21},27248},{{37,35,22},74000},{{37,35,23},158272},{{37,35,24},178816},{{37,35,25},417600},{{37,35,26},854112},{{37,35,27},1237152},{{37,35,28},1733888},{{37,35,29},4738112},{{37,35,30},4512256},{{37,35,31},13988480},{{37,35,32},22712320},{{37,35,33},34185216},{{37,35,34,1},1},{{37,35,34,2},1},{{37,35,34,3},2},{{37,35,34,4},2},{{37,35,34,5},6},{{37,35,34,6},8},{{37,35,34,7},20},{{37,35,34,8},32},{{37,35,34,9},56},{{37,35,34,10},56},{{37,35,34,11},184},{{37,35,34,12},216},{{37,35,34,13},584},{{37,35,34,14},552},{{37,35,34,15},792},{{37,35,34,16},2112},{{37,35,34,17},4624},{{37,35,34,18},7128},{{37,35,34,19},16376},{{37,35,34,20},16800},{{37,35,34,21},24448},{{37,35,34,22},73520},{{37,35,34,23},147520},{{37,35,34,24},166272},{{37,35,34,25},392800},{{37,35,34,26},852544},{{37,35,34,27},1188544},{{37,35,34,28},1692672},{{37,35,34,29},4587872},{{37,35,34,30},4477952},{{37,35,34,31},13653696},{{37,35,34,32},22315008},{{37,35,34,33},33287808},{{37,36,1},1},{{37,36,2},1},{{37,36,3},2},{{37,36,4},4},{{37,36,5},8},{{37,36,6},12},{{37,36,7},28},{{37,36,8},24},{{37,36,9},64},{{37,36,10},84},{{37,36,11},228},{{37,36,12},384},{{37,36,13},840},{{37,36,14},1248},{{37,36,15},1408},{{37,36,16},2784},{{37,36,17},7120},{{37,36,18},9792},{{37,36,19},24032},{{37,36,20},33024},{{37,36,21},45024},{{37,36,22},113248},{{37,36,23},239360},{{37,36,24},154752},{{37,36,25},436160},{{37,36,26},1008128},{{37,36,27},925440},{{37,36,28},2274752},{{37,36,29},5277952},{{37,36,30},4341504},{{37,36,31},14897408},{{37,36,32},25112576},{{37,36,33},35796480},{{37,36,34,2},1},{{37,36,34,3},1},{{37,36,34,4},2},{{37,36,34,5},4},{{37,36,34,6},8},{{37,36,34,7},16},{{37,36,34,8},16},{{37,36,34,9},36},{{37,36,34,10},84},{{37,36,34,11},168},{{37,36,34,12},288},{{37,36,34,13},624},{{37,36,34,14},1248},{{37,36,34,15},1152},{{37,36,34,16},2432},{{37,36,34,17},6080},{{37,36,34,18},9280},{{37,36,34,19},21440},{{37,36,34,20},30720},{{37,36,34,21},39648},{{37,36,34,22},113248},{{37,36,34,23},226496},{{37,36,34,24},145152},{{37,36,34,25},409984},{{37,36,34,26},1008128},{{37,36,34,27},897280},{{37,36,34,28},2228224},{{37,36,34,29},5141760},{{37,36,34,30},4311552},{{37,36,34,31},14595072},{{37,36,34,32},24725504},{{37,36,34,33},34956288},{{37,36,35,1},1},{{37,36,35,2},1},{{37,36,35,3},2},{{37,36,35,4},4},{{37,36,35,5},8},{{37,36,35,6},12},{{37,36,35,7},28},{{37,36,35,8},24},{{37,36,35,9},64},{{37,36,35,10},42},{{37,36,35,11},186},{{37,36,35,12},312},{{37,36,35,13},684},{{37,36,35,14},468},{{37,36,35,15},704},{{37,36,35,16},1608},{{37,36,35,17},4148},{{37,36,35,18},5456},{{37,36,35,19},13752},{{37,36,35,20},15616},{{37,36,35,21},20320},{{37,36,35,22},55856},{{37,36,35,23},119296},{{37,36,35,24},77376},{{37,36,35,25},269184},{{37,36,35,26},549440},{{37,36,35,27},507616},{{37,36,35,28},1110304},{{37,36,35,29},2752512},{{37,36,35,30},2211840},{{37,36,35,31},7716864},{{37,36,35,32},12974592},{{37,36,35,33},18982656},{{37,36,35,34},23385479},{{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++) {
      |                          ~^~~~~~~~~

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Correct	0 ms	616 KB	Output is correct
5	Correct	1 ms	616 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct

Subtask #2

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Correct	0 ms	616 KB	Output is correct
5	Correct	1 ms	616 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	87 ms	600 KB	Output is correct
8	Correct	84 ms	600 KB	Output is correct
9	Correct	49 ms	604 KB	Output is correct
10	Correct	118 ms	604 KB	Output is correct
11	Correct	33 ms	624 KB	Output is correct
12	Correct	63 ms	604 KB	Output is correct

Subtask #3

0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Correct	0 ms	616 KB	Output is correct
5	Correct	1 ms	616 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	87 ms	600 KB	Output is correct
8	Correct	84 ms	600 KB	Output is correct
9	Correct	49 ms	604 KB	Output is correct
10	Correct	118 ms	604 KB	Output is correct
11	Correct	33 ms	624 KB	Output is correct
12	Correct	63 ms	604 KB	Output is correct
13	Execution timed out	4061 ms	604 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Correct	0 ms	616 KB	Output is correct
5	Correct	1 ms	616 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	87 ms	600 KB	Output is correct
8	Correct	84 ms	600 KB	Output is correct
9	Correct	49 ms	604 KB	Output is correct
10	Correct	118 ms	604 KB	Output is correct
11	Correct	33 ms	624 KB	Output is correct
12	Correct	63 ms	604 KB	Output is correct
13	Execution timed out	4061 ms	604 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #5

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Correct	0 ms	616 KB	Output is correct
5	Correct	1 ms	616 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	87 ms	600 KB	Output is correct
8	Correct	84 ms	600 KB	Output is correct
9	Correct	49 ms	604 KB	Output is correct
10	Correct	118 ms	604 KB	Output is correct
11	Correct	33 ms	624 KB	Output is correct
12	Correct	63 ms	604 KB	Output is correct
13	Execution timed out	4061 ms	604 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-