oj.uz

답안 #1066827

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1066827 2024-08-20T07:47:49 Z 정민찬(#11123) Present (RMI21_present) C++17
29 / 100
 4000 ms 624 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},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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -