fork download
copy 
  1. /*
  2. * @Author: hungeazy
  3. * @Date:   2026-02-28 14:02:04
  4. * @Last Modified by:   hungeazy
  5. * @Last Modified time: 2026-02-28 14:42:40
  6. */
  7. #include <bits/stdc++.h>
  8. #include <ext/pb_ds/assoc_container.hpp> 
  9. #include <ext/pb_ds/tree_policy.hpp> 
  10. // #pragma GCC optimize("O3")  
  11. // #pragma GCC optimize("unroll-loops")  
  12. // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
  13. using namespace std;
  14. using namespace __gnu_pbds; 
  15. bool M1;
  16. #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  17. #define int long long
  18. #define ll long long 
  19. #define ull unsigned long long
  20. #define sz(x) x.size()
  21. #define sqr(x) (1LL * (x) * (x))
  22. #define all(x) x.begin(), x.end()
  23. #define fill(f,x) memset(f,x,sizeof(f))
  24. #define FOR(i,l,r) for(int i=l;i<=r;i++)
  25. #define FOD(i,r,l) for(int i=r;i>=l;i--)
  26. #define debug(x) cout << #x << " = " << x << '\n'
  27. #define ii pair<int,int>
  28. #define iii pair<int,ii>
  29. #define di pair<ii,ii>
  30. #define vi vector<int>
  31. #define vii vector<ii>
  32. #define mii map<int,int>
  33. #define fi first
  34. #define se second
  35. #define pb push_back
  36. #define MOD 1000000007
  37. #define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
  38. #define YES cout << "YES\n"
  39. #define NO cout << "NO\n"
  40. #define MASK(i) (1LL << (i))
  41. #define c_bit(i) __builtin_popcountll(i)
  42. #define BIT(x,i) ((x) & MASK(i))
  43. #define SET_ON(x,i) ((x) | MASK(i))
  44. #define SET_OFF(x,i) ((x) & ~MASK(i))
  45. #define oo 1e18
  46. #define name "HOAN_VI_DEP"
  47. #define endl '\n'
  48. #define memory() cerr << abs(&M2-&M1)/1024.0/1024 << " MB" << endl
  49. #define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms." << endl
  50. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
  51. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
  52. template <class T> using ordered_set = tree <T, null_type, less_equal <T>, rb_tree_tag,tree_order_statistics_node_update>;
  53. int n,m,k;
  54.  
  55. namespace sub1 {
  56.  
  57. 	bool approved() {
  58. 		return n <= 10 and k <= 1e5;
  59. 	}
  60.  
  61. 	void solve(void)
  62. 	{
  63. 		vi perm, ans, first;
  64. 		FOR(i,1,n) perm.pb(i);
  65. 		int dem = 0;
  66. 		bool check = false;
  67. 		do {
  68. 			int cnt = 0;
  69. 			FOR(i,0,n-1)
  70. 				FOR(j,i+1,n-1)
  71. 					cnt += (perm[i] > perm[j]);
  72. 			dem += (cnt == m);
  73. 			if (dem == k)
  74. 			{
  75. 				ans = perm;
  76. 				check = true;
  77. 				break;
  78. 			}
  79. 		} while (next_permutation(all(perm)));
  80. 		if (!check)
  81. 		{
  82. 			cout << -1;
  83. 			return;
  84. 		}
  85. 		vii vec;
  86. 		FOR(i,0,n-1) 
  87. 			if (ans[i] != i+1) vec.pb({i+1,ans[i]});
  88. 		cout << sz(vec) << endl;
  89. 		for (auto [x,y] : vec) cout << x << " " << y << endl;
  90. 	}
  91.  
  92. }
  93.  
  94. namespace sub2 {
  95.  
  96. 	const int N = (int)1e3+10, M = 210;
  97. 	int dp[N][M],pre[M],ans[N];
  98.  
  99. 	bool approved() {
  100. 		return n <= 1e3 and k <= 1e9;
  101. 	}
  102.  
  103. 	void solve(void)
  104. 	{
  105. 		int mxInv = n*(n-1)/2;
  106. 		if (m > mxInv)
  107. 		{
  108. 			cout << -1;
  109. 			return;
  110. 		}
  111. 		dp[0][0] = 1;
  112. 		FOR(i,1,n)
  113. 		{
  114. 			FOR(j,1,m) pre[j] = 0;
  115. 			pre[0] = dp[i-1][0];
  116. 			FOR(j,1,m) pre[j] = min((int)oo,pre[j-1]+dp[i-1][j]);
  117. 			FOR(j,0,m)
  118. 			{
  119. 				int val = pre[j];
  120. 				if (j-i >= 0) val -= pre[j-i];
  121. 				if (val < 0) val = 0;
  122. 				dp[i][j] = min((int)oo,val);
  123. 			}
  124. 		}
  125. 		if (dp[n][m] < k)
  126. 		{
  127. 			cout << -1;
  128. 			return;
  129. 		}
  130. 		vi perm(n);
  131. 		iota(all(perm),1);
  132. 		int cur = m, len = n;
  133. 		FOR(pos,1,n)
  134. 			FOR(r,1,len)
  135. 			{
  136. 				int cost = r-1;
  137. 				if (cost > cur) break;
  138. 				int cnt = dp[len-1][cur-cost];
  139. 				if (cnt >= k)
  140. 				{
  141. 					ans[pos] = perm[r-1];
  142. 					perm.erase(perm.begin()+(r-1));
  143. 					cur -= cost;
  144. 					len--;
  145. 					break;
  146. 				}
  147. 				else k -= cnt;
  148. 			}
  149. 		vii vec;
  150. 		FOR(i,1,n)
  151. 			if (ans[i] != i) vec.pb({i,ans[i]});
  152. 		cout << sz(vec) << endl;
  153. 		for (auto [x,y] : vec) cout << x << " " << y << endl;
  154. 	}
  155.  
  156. }
  157.  
  158. bool M2;
  159. signed main()
  160. {
  161.     fast;
  162.     if (fopen(name".inp","r"))
  163.     {
  164.     	freopen(name".inp","r",stdin);
  165.     	freopen(name".out","w",stdout);
  166.     }
  167.     cin >> n >> m >> k;
  168.     if (sub1::approved()) return sub1::solve(), time(), memory(), 0;
  169.     if (sub2::approved()) return sub2::solve(), time(), memory(), 0;
  170.     time();
  171.     memory();
  172.     return 0;
  173. }
  174. // ██░ ██  █    ██  ███▄    █   ▄████
  175. //▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
  176. //▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
  177. //░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
  178. //░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
  179. // ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
  180. // ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
  181. // ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
  182. // ░  ░  ░   ░              ░       ░
Success #stdin #stdout #stderr 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
stderr
copy 
-------------Time:5.984ms.
1.62759 MB
https://ideone.com/3ekciD
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!