fork download
copy 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "graph"
  7. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  8. #define ffr(i, b, a) for(auto i=(b); b>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. //#define pb push_back
  12. #define pb emplace_back
  13. #define fi first
  14. #define se second
  15. #define sz(s) (int)s.size()
  16. #define all(s) (s).begin(), (s).end()
  17. #define ms(a,x) memset(a, x, sizeof (a))
  18. #define cn continue
  19. #define re exit(0)
  20.  
  21. typedef long long ll;
  22. typedef unsigned long long ull;
  23. typedef long double ld;
  24. typedef vector<int> vi;
  25. typedef vector<ll> vll;
  26. typedef pair<int, int> pii;
  27. typedef pair<ll, ll> pll;
  28. typedef vector<pii> vpii;
  29. typedef vector<pll> vpll;
  30.  
  31. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  32. ll ran(ll l, ll r)
  33. {
  34.     return uniform_int_distribution<ll> (l, r)(rng);
  35. }
  36.  
  37. inline void rf()
  38. {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(nullptr); cout.tie(nullptr);
  41.     if(fopen(file".inp","r"))
  42.     {
  43.         freopen(file".inp","r",stdin);
  44.         freopen(file".out","w",stdout);
  45.     }
  46. }
  47.  
  48. const int mod=1e9+19972207;
  49. const int maxn=1e5+15;
  50. const ll inf=5e16;
  51.  
  52. template<typename T> inline void add(T &x, const T &y)
  53. {
  54.     x+=y;
  55.     if(x>=mod) x-=mod;
  56.     if(x<0) x+=mod;
  57. }
  58.  
  59. template<typename T> inline bool maxi(T &a, T b)
  60. {
  61.     if(a>=b) return 0;
  62.     a=b; return 1;
  63. }
  64.  
  65. template<typename T> inline bool mini(T &a, T b)
  66. {
  67.     if(a<=b) return 0;
  68.     a=b; return 1;
  69. }
  70.  
  71. int diss, numPair;
  72. int numNode;
  73. vector<pair<int, int>> edges;
  74.  
  75. void init(void) {
  76. 	cin >> diss >> numPair;
  77. }
  78. void print(void) {
  79. 	cout << numNode << " " << edges.size() << "\n";
  80. 	for (const pair<int, int> &e : edges) cout << e.fi << " " << e.se << "\n";
  81. }
  82.  
  83. namespace general {
  84. 	bool check(void) {
  85. 		return diss > 2;
  86. 	}
  87.  
  88. 	void createComponent(int x, int y) {
  89. 		int left_center = ++numNode;
  90. 		int cur = left_center;
  91. 		ff(i, 1, diss) {
  92. 			int tmp = ++numNode;
  93. 			edges.push_back({cur, tmp});
  94. 			cur = tmp;
  95. 		}
  96. 		int right_center = cur;
  97.  
  98. 		ff(i, 1, x) edges.push_back({left_center, ++numNode});
  99. 		ff(i, 1, y) edges.push_back({right_center, ++numNode});
  100. 	}
  101.  
  102. 	void solve(void) {
  103. 		while (numPair > 0) {
  104.  
  105.             int N_remain = 1000 - numNode;
  106.             int M_remain = 1000 - (int)edges.size();
  107.  
  108.             if (N_remain < diss + 3) break;
  109.             if (M_remain < diss + 2) break;
  110.  
  111. 			// 1. Tìm t max sao cho t^2 <= numPair (Logic Cauchy ban đầu)
  112. 			int t_optimal = 1;
  113. 			while ((ll)(t_optimal + 1) * (t_optimal + 1) <= numPair) t_optimal++;
  114.  
  115.             // 2. Giới hạn t bởi N và M
  116.             int limit_sum_N = N_remain - (diss + 1);
  117.             int limit_sum_M = M_remain - diss;
  118.             int limit_sum = min(limit_sum_N, limit_sum_M);
  119.  
  120.             int t_limit = limit_sum / 2;
  121.             if (t_limit < 1) t_limit = 1;
  122.  
  123.             int t = min(t_optimal, t_limit);
  124.             if (t < 1) t = 1;
  125.  
  126.             // 3. Tạo TPLT với x=y=t
  127.             int x = t;
  128.             int y = t;
  129.  
  130.             ll pairs_to_create = (ll)x * y;
  131.  
  132.             if (pairs_to_create > numPair) {
  133.                 // Điều này chỉ xảy ra khi t_optimal được tính quá sát limit_sum/2
  134.                 // Trong trường hợp này, ta phải giảm x, y sao cho x*y = numPair và x+y nhỏ nhất
  135.                 int P = numPair;
  136.  
  137.                 x = (int)sqrt(P);
  138.                 while(P % x != 0) x--;
  139.                 y = P / x;
  140.  
  141.                 // Kiểm tra lại giới hạn sum (Nếu t_optimal quá lớn)
  142.                 if (x + y > limit_sum) {
  143.                     x = 1;
  144.                     y = limit_sum - 1;
  145.                     if (y < 1) break;
  146.                     pairs_to_create = min((ll)P, (ll)x * y);
  147.                     y = (int)pairs_to_create; // x=1, y=P
  148.                 } else {
  149.                     pairs_to_create = (ll)x * y;
  150.                 }
  151.             }
  152.  
  153.             // Kiểm tra lại lần cuối
  154.             if (x == 0 || y == 0 || x + y > limit_sum) break;
  155.  
  156.             if (x > 0 && y > 0 && pairs_to_create > 0) {
  157.                 createComponent(x, y);
  158.                 numPair -= pairs_to_create;
  159.             } else {
  160.                 break;
  161.             }
  162. 		}
  163. 	}
  164. }
  165.  
  166. namespace special {
  167. 	bool check(void) {
  168. 		return diss == 2;
  169. 	}
  170.  
  171. 	void createComponent(int t) {
  172. 		int u = ++numNode;
  173. 		ff(i, 1, t) edges.push_back({u, ++numNode});
  174. 	}
  175.  
  176. 	void solve(void) { 
  177. 		while (numPair > 0) {
  178.  
  179.             int N_remain = 1000 - numNode;
  180.             int M_remain = 1000 - (int)edges.size();
  181.  
  182.             if (N_remain < 3 || M_remain < 2) break;
  183.  
  184.             // 1. Tối ưu: t max sao cho t*(t-1)/2 <= numPair
  185.             int t_optimal = 2;
  186.             while ((ll)(t_optimal + 1) * t_optimal / 2 <= numPair) t_optimal++;
  187.             t_optimal--;
  188.  
  189.             // 2. Giới hạn t bởi N và M
  190.             int limit_t_N = N_remain - 1;
  191.             int limit_t_M = M_remain;
  192.  
  193.             int limit_t = min({t_optimal, limit_t_N, limit_t_M});
  194.             if (limit_t < 2) break;
  195.  
  196.             int t = limit_t;
  197.  
  198.             ll pairs_created = (ll)t * (t - 1) / 2;
  199.  
  200.             if (pairs_created > numPair) {
  201.                 // Điều này không nên xảy ra nếu t đã được giới hạn bởi t_optimal
  202.                 // Nhưng nếu xảy ra, ta phải giảm t xuống.
  203.                 t = 2;
  204.                 while ((ll)(t + 1) * t / 2 <= numPair) t++;
  205.                 t--;
  206.  
  207.                 t = min(t, limit_t);
  208.                 pairs_created = (ll)t * (t - 1) / 2;
  209.             }
  210.  
  211.             if (t < 2 || pairs_created <= 0) break;
  212.  
  213.             if (pairs_created > 0) {
  214.                 createComponent(t);
  215.                 numPair -= pairs_created;
  216.             } else {
  217.                 break;
  218.             }
  219. 		}
  220. 	}
  221. }
  222.  
  223. void process(void) {
  224. 	if (general::check()) {
  225. 		general::solve();
  226. 	} else if (special::check()) {
  227. 		special::solve();
  228. 	}
  229. }
  230.  
  231. signed main()
  232. {
  233.     rf();
  234.     init();
  235.     process();
  236.     print();
  237.     return 0;
  238. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5 2
stdout
copy 
16 14
1 2
2 3
3 4
4 5
5 6
1 7
6 8
9 10
10 11
11 12
12 13
13 14
9 15
14 16
https://ideone.com/lXPyP9
language:
C++14 (gcc 8.3)
created:
1 day 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!