#pragma GCC optimize("Ofast") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #define satori int bepis;cin >> bepis;while(bepis--) #define st first #define nd second #define mp make_pair //#define int long long using namespace std; int part(int &k, vector<pair<int,int>> &v,vector<int> &power) { if(k == 1) { v.push_back(mp(0,-1)); k--; return 2137; } v.push_back(mp(0,-1)); v.push_back(mp(0,-1)); int x = 2; while(x<=k) { power.push_back(v.size()-2); v.push_back(mp(v.size()-2,v.size()-1)); v.push_back(v.back()); x*=2; } power.push_back(v.size()-2); v.push_back(mp(v.size()-2,v.size()-1)); v.push_back(v.back()); return 2137; } int pr(int k) { int x = 2; int i = 1; int b = 1; while(i<32) { //cout << i*2<<' '<<i*2+1<<'\n'; if(i==b*2 - 1) { b*=2; x=x*x; } i++; } return i+b-1; } int print(int k,int &b) { int x = 2; int i = 1; b = 1; while(i<32) { cout << i*2<<' '<<i*2+1<<'\n'; if(i==b*2 - 1) {b*=2; x*=x;} i++; } return i+b-1; } int32_t main() { std::ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int k; cin >> k; if(k==1) { cout << 2 << '\n'; cout << -1 << ' ' << 2 << '\n'; cout << -1 << ' ' << -1 << '\n'; return 0; } vector<pair<int,int>> ans; ans.push_back(mp(-1,-1)); vector<int> power; part(k,ans,power); reverse(ans.begin(),ans.end()); int b; int n = ans.size() +32; //+ pr(k); //int n = ans.size(); cout << n<<'\n'; //print(k,b); int x = 1; for(int i = 0;i<31;i++) { if( (k&(-k)) == x) { cout << n-power[i]; k-=x; }else cout << -1; cout << ' ' << i+2 << '\n'; x*=2; } cout << -1 << ' '<<-1<<'\n'; for(auto x :ans){ if(x.st == -1)cout << x.st; else cout << n-x.st; cout <<' '; if(x.nd == -1)cout << x.nd; else cout << n-x.nd; cout <<'\n'; } //cout << k; // for(int x:power)cout << x << ' '; }
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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | #pragma GCC optimize("Ofast") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #define satori int bepis;cin >> bepis;while(bepis--) #define st first #define nd second #define mp make_pair //#define int long long using namespace std; int part(int &k, vector<pair<int,int>> &v,vector<int> &power) { if(k == 1) { v.push_back(mp(0,-1)); k--; return 2137; } v.push_back(mp(0,-1)); v.push_back(mp(0,-1)); int x = 2; while(x<=k) { power.push_back(v.size()-2); v.push_back(mp(v.size()-2,v.size()-1)); v.push_back(v.back()); x*=2; } power.push_back(v.size()-2); v.push_back(mp(v.size()-2,v.size()-1)); v.push_back(v.back()); return 2137; } int pr(int k) { int x = 2; int i = 1; int b = 1; while(i<32) { //cout << i*2<<' '<<i*2+1<<'\n'; if(i==b*2 - 1) { b*=2; x=x*x; } i++; } return i+b-1; } int print(int k,int &b) { int x = 2; int i = 1; b = 1; while(i<32) { cout << i*2<<' '<<i*2+1<<'\n'; if(i==b*2 - 1) {b*=2; x*=x;} i++; } return i+b-1; } int32_t main() { std::ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int k; cin >> k; if(k==1) { cout << 2 << '\n'; cout << -1 << ' ' << 2 << '\n'; cout << -1 << ' ' << -1 << '\n'; return 0; } vector<pair<int,int>> ans; ans.push_back(mp(-1,-1)); vector<int> power; part(k,ans,power); reverse(ans.begin(),ans.end()); int b; int n = ans.size() +32; //+ pr(k); //int n = ans.size(); cout << n<<'\n'; //print(k,b); int x = 1; for(int i = 0;i<31;i++) { if( (k&(-k)) == x) { cout << n-power[i]; k-=x; }else cout << -1; cout << ' ' << i+2 << '\n'; x*=2; } cout << -1 << ' '<<-1<<'\n'; for(auto x :ans){ if(x.st == -1)cout << x.st; else cout << n-x.st; cout <<' '; if(x.nd == -1)cout << x.nd; else cout << n-x.nd; cout <<'\n'; } //cout << k; // for(int x:power)cout << x << ' '; } |