fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i, a, b) for (int i = a; i <= b; ++i)
  3. #define FORD(i, a, b) for (int i = a; i >= b; --i)
  4. #define ll long long
  5.  
  6. using namespace std;
  7.  
  8. int d, k, cur;
  9. vector<pair<int, int>> Edges;
  10.  
  11. void nhap() {
  12.     cin >> d >> k;
  13. }
  14.  
  15. int Find(int k) {
  16.     int l = 1, r = k, res = 0;
  17.     while (l <= r) {
  18.         int m = (l + r) >> 1;
  19.         if (1ll * m * (m + 1) <= 2 * k) res = m, l = m + 1;
  20.         else r = m - 1;
  21.     }
  22.     return res;
  23. }
  24.  
  25. // d = 2
  26. void sub1() {
  27.     while (k) {
  28.         int T = Find(k);
  29.         int node = ++cur;
  30.         FOR(i, 1, T + 1) {
  31.             ++cur;
  32.             Edges.push_back({node, cur});
  33.         }
  34.         k -= 1ll * T * (T + 1) / 2;
  35.     }
  36. }
  37.  
  38. // d >= 3
  39. void sub2() {
  40.     while (k) {
  41.         int st = ++cur;
  42.         int last = st;
  43.         FOR(i, 3, d) {
  44.             Edges.push_back({last, ++cur});
  45.             last = cur;
  46.         }
  47.         int ed = cur;
  48.         int T = sqrt(k);
  49.         FOR(i, 1, T) {
  50.             int a = ++cur, b = ++cur;
  51.             Edges.push_back({st, a});
  52.             Edges.push_back({ed, b});
  53.         }
  54.         k -= T * T;
  55.     }
  56. }
  57.  
  58. void giai() {
  59.     if (d == 2) sub1();
  60.     else sub2();
  61.  
  62.     cout << cur << ' ' << Edges.size() << '\n';
  63.     for (auto [u, v] : Edges)
  64.         cout << u << ' ' << v << '\n';
  65. }
  66.  
  67. int main() {
  68.     ios_base::sync_with_stdio(0);
  69.     cin.tie(0); cout.tie(0);
  70.  
  71.     #define name "graph"
  72.  
  73.     if (fopen(name".inp", "r")) {
  74.         freopen(name".inp", "r", stdin);
  75.         freopen(name".out", "w", stdout);
  76.     }
  77.  
  78.     nhap();
  79.     giai();
  80.  
  81.     return 0;
  82. }
  83.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/V1MQqT
language:
C++14 (clang 8.0)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!