Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2018
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.44 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define F first
  4. #define S second
  5. #define pb push_back
  6. #define ll long long
  7. #define ld long double
  8. #define pii pair <int,int>
  9. #define endl '\n'
  10. #define FILE "nenokku_easy"
  11.  
  12. #pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")
  13.  
  14. using namespace std;
  15.  
  16. const int mod = 1e9 + 7;
  17. const int N = 100000;
  18. const ll inf = 1e18;
  19.  
  20. int rd() {
  21. return (rand() << 15 | rand());
  22. }
  23.  
  24. int in[N + 5];
  25.  
  26. int main() {
  27. ios_base::sync_with_stdio(0);
  28. cin.tie(0);
  29. cout.tie(0);
  30. srand(time(0));
  31. #ifdef LOCAL
  32. // freopen("input.txt", "r", stdin);
  33. freopen("input.txt", "w", stdout);
  34. #else
  35. //freopen(FILE".in", "r", stdin);
  36. // freopen(FILE".out", "w", stdout);
  37. #endif
  38. int t = 1;
  39. while (t--) {
  40. int n = N;
  41. n = max(n, 2);
  42. cout << n << endl;
  43. int root = rd() % n + 1;
  44. int cnt = rd() % n + 1;
  45. cnt = min(cnt, n - 1);
  46. vector <int> used;
  47. vector <int> perm;
  48. for (int i = 1; i <= n; i++) {
  49. if (i == root) continue;
  50. perm.pb(i);
  51. }
  52. int all = n - 1;
  53. random_shuffle(perm.begin(), perm.end());
  54. cnt = min(cnt,(int)perm.size());
  55. int it = 1;
  56. int e = n - 1 - cnt;
  57. int st = 0;
  58. for (int i = 0; i < cnt; i++) {
  59. if (all == 0) break;
  60. cout << root << " " << perm[st] << endl;
  61. in[root]++;
  62. in[perm[st]]++;
  63. it++;
  64. used.pb(perm[st]);
  65. st++;
  66. all--;
  67. }
  68. random_shuffle(used.begin(), used.end());
  69. unordered_set <int> good;
  70. for (auto x : used) good.insert(x);
  71. int id = 1, sq = (int)sqrt(N);
  72. for (int i = 0; ; i++) {
  73. if (all == 0) break;
  74. int cur = root;
  75. if (good.size()) {
  76. cur = *good.begin();
  77. good.erase(good.begin());
  78. }
  79. in[cur]++;
  80. in[perm[i + st]]++;
  81. cout << cur << " " << perm[i + st] << endl;
  82. // cerr << cur << " " << perm[i + st] << endl;
  83. good.insert(perm[i + st]);
  84. if (id % 100 == 0) {
  85. vector <int> kek;
  86. for (auto x : good) kek.pb(x);
  87. good.clear();
  88. random_shuffle(kek.begin(), kek.end());
  89. for (auto x : kek) good.insert(x);
  90. }
  91. id++;
  92. it++;
  93. all--;
  94. }
  95. //int q = rd() % (3 * N) + 1;
  96. int q = 3 * N;
  97. cout << q << endl;
  98. int x = rd() % n + 1;
  99. cout << 3 << " " << x << " ";
  100. x = rd() % n + 1;
  101. cout << x << endl;
  102. q--;
  103. while (q--) {
  104. int type = rand() % 50 + 1;
  105. cout << min(type, 3) << " ";
  106. if (type == 1) {
  107. int x = rd() % (n - 1) + 1;
  108. cout << x << endl;
  109. continue;
  110. }
  111. if (type == 2) {
  112. int x = rd() % (n - 1) + 1;
  113. cout << x << endl;
  114. continue;
  115. }
  116. {
  117. int x = rd() % n + 1;
  118. cout << x << " ";
  119. int y = rd() % n + 1;
  120. if (x == y && rd() % 10 != 3){
  121. while (x == y) y = rd() % n + 1;
  122. }
  123. cout << y << endl;
  124. }
  125. }
  126. }
  127. return 0;
  128. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement