#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<ll> vl; typedef vector<vector<ll>> vvl; #define pb push_back #define eb emplace_back #define mp make_pair #define mt make_tuple #define st first #define nd second #define FOR(__VAR, __START, __END) for(int __VAR=__START; __VAR<=__END; __VAR++) #define FORB(__VAR, __START, __END) for(int __VAR=__START; __VAR>=__END; __VAR--) #define FORK(__VAR, __START, __END, __DIFF) for(int __VAR=__START; __VAR<=END; __VAR+=__DIFF) #define all(__VAR) (__VAR).begin(), (__VAR).end() #define rall(__VAR) (__VAR).rbegin(), (__VAR).rend() #define DEBUG(__VAR) cout << #__VAR << ": " << __VAR << endl; template<typename __T1, typename __T2> ostream & operator<<(ostream &out, pair<__T1, __T2> &__VAR) { cout << "[" << __VAR.st << ", " << __VAR.nd << "]"; return out; } template<typename __T> ostream & operator<<(ostream &out, vector<__T> &__VAR) { cout << "["; FOR(i, 0, (int)__VAR.size()-2) cout << __VAR[i] << ", "; if(__VAR.size()>0) cout << __VAR[__VAR.size()-1]; cout << "]" << endl; return out; } const int INF=1e9; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int k; cin >> k; int K=k; int n=59+__builtin_popcount(k); vector<pii> g(n+1, {-1,-1}); queue<int> que; for(int i=n-59+1; i<n; i+=2) if(i+2<=n) g[i].nd=i+2; for(int i=n-59+1; i<n; i++) if(i+1<=n) g[i].st=i+1; for(int i=n; i>=0 && k>0; i-=2,k/=2) if(k&1) que.push(i); for(int i=n-59; i>1; i--) { int a=que.front(); que.pop(); int b=que.front(); que.pop(); g[i]={a,b}; que.push(i); } if(__builtin_popcount(K)==1) g[1].st=que.front(); else g[1].st=2; cout << n << '\n'; for(int i=1; i<=n; i++) cout << g[i].st << ' ' << g[i].nd << '\n'; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 | #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<ll> vl; typedef vector<vector<ll>> vvl; #define pb push_back #define eb emplace_back #define mp make_pair #define mt make_tuple #define st first #define nd second #define FOR(__VAR, __START, __END) for(int __VAR=__START; __VAR<=__END; __VAR++) #define FORB(__VAR, __START, __END) for(int __VAR=__START; __VAR>=__END; __VAR--) #define FORK(__VAR, __START, __END, __DIFF) for(int __VAR=__START; __VAR<=END; __VAR+=__DIFF) #define all(__VAR) (__VAR).begin(), (__VAR).end() #define rall(__VAR) (__VAR).rbegin(), (__VAR).rend() #define DEBUG(__VAR) cout << #__VAR << ": " << __VAR << endl; template<typename __T1, typename __T2> ostream & operator<<(ostream &out, pair<__T1, __T2> &__VAR) { cout << "[" << __VAR.st << ", " << __VAR.nd << "]"; return out; } template<typename __T> ostream & operator<<(ostream &out, vector<__T> &__VAR) { cout << "["; FOR(i, 0, (int)__VAR.size()-2) cout << __VAR[i] << ", "; if(__VAR.size()>0) cout << __VAR[__VAR.size()-1]; cout << "]" << endl; return out; } const int INF=1e9; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int k; cin >> k; int K=k; int n=59+__builtin_popcount(k); vector<pii> g(n+1, {-1,-1}); queue<int> que; for(int i=n-59+1; i<n; i+=2) if(i+2<=n) g[i].nd=i+2; for(int i=n-59+1; i<n; i++) if(i+1<=n) g[i].st=i+1; for(int i=n; i>=0 && k>0; i-=2,k/=2) if(k&1) que.push(i); for(int i=n-59; i>1; i--) { int a=que.front(); que.pop(); int b=que.front(); que.pop(); g[i]={a,b}; que.push(i); } if(__builtin_popcount(K)==1) g[1].st=que.front(); else g[1].st=2; cout << n << '\n'; for(int i=1; i<=n; i++) cout << g[i].st << ' ' << g[i].nd << '\n'; return 0; } |