fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define rep(i,a,b) for (int i=a; i<b; i++)
  3. #define all(x) (x).begin(),(x).end()
  4. #define pb push_back
  5. #define mp make_pair
  6. #define fi first
  7. #define se second
  8. #define debug printf
  9. using namespace std;
  10. typedef long long ll;
  11. typedef long double ld;
  12. typedef pair<int, int> PII;
  13.  
  14. const int MX = (int)1e5 + 5, MK = 200;
  15.  
  16. map < int, int > skala;
  17. int reskala[MX];
  18. vector < PII > ans;
  19. int moves;
  20.  
  21. vector < int > V[MX], S;
  22. int p10[100];
  23.  
  24. int cy(int x, int pos)
  25. {
  26. 	return ((x / p10[pos]) % 10);
  27. }
  28.  
  29. void rusz(int x, int y)
  30. {
  31. 	moves--;
  32. 	ans.pb({x, y});
  33. 	//printf("%d %d\n", x, y);
  34. 	assert(V[x].size());
  35. 	V[y].pb(V[x].back());
  36. 	V[x].pop_back();
  37. }
  38.  
  39. int main ()
  40. {
  41. 	int n, k;
  42. 	scanf("%d%d", &n, &k);
  43. 	moves = 13 * n;
  44. 	for(int i = 1; i <= k; ++i)
  45. 	{
  46. 		int t;
  47. 		scanf("%d", &t);
  48. 		for(int j = 1; j <= t; ++j)
  49. 		{
  50. 			int a;
  51. 			scanf("%d", &a);
  52. 			V[i].pb(a);
  53. 			S.pb(a);
  54. 		}
  55. 		reverse(all(V[i]));
  56. 	}
  57. 	sort(all(S));
  58. 	for(int i = 0; i < n; ++i)
  59. 	{
  60. 		skala[S[i]] = i;
  61. 		reskala[i] = S[i];
  62. 	}
  63. 	for(int i = 1; i <= k; ++i)
  64. 		for(auto &v : V[i])
  65. 			v = skala[v];
  66. 	for(int i = 1; i < k; ++i)
  67. 		while(V[i].size())
  68. 			rusz(i, k);
  69. 	p10[0] = 1;
  70. 	for(int i = 1; i < 10; ++i)
  71. 		p10[i] = 10 * p10[i - 1];
  72. 	for(int cyf = 4; cyf >= 0; --cyf)
  73. 	{
  74. 		while(V[k].size())
  75. 		{
  76. 			int gdzie = 1 + cy(V[k].back(), cyf);
  77. 			rusz(k, gdzie);
  78. 		}
  79. 		for(int oc = 9; oc >= 0; --oc)
  80. 			for(int i = 10; i > 0; --i)
  81. 				while(V[i].size() && cy(V[i].back(), cyf + 1) == oc)
  82. 					rusz(i, k);
  83. 		/*for(int i = 1; i <= k; ++i)
  84. 		{
  85. 			printf("\n%d ", (int)V[i].size());
  86. 			for(auto v : V[i])
  87. 				printf("%d ", v);
  88. 		}*/
  89. 	}
  90. 	int ile = n / k;
  91. 	for(int i = 1; i < k; ++i)
  92. 	{
  93. 		int pom = ((i == 1) ? 2 : 1); 
  94. 		for(int j = 1; j <= ile; ++j)
  95. 			rusz(k, pom);
  96. 		for(int j = 1; j <= ile; ++j)
  97. 			rusz(pom, i);
  98. 	}
  99. 	assert(moves >= 0);
  100. 	printf("%d\n", (int)ans.size());
  101. 	for(auto v : ans)
  102. 		printf("%d %d\n", v.fi, v.se);
  103. 	/*for(int i = 1; i <= k; ++i)
  104. 	{
  105. 		printf("\n%d ", (int)V[i].size());
  106. 		for(auto v : V[i])
  107. 			printf("%d ", reskala[v]);
  108. 	}*/
  109.  
  110. }
Success #stdin #stdout 0s 6056KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/0V1swh
language:
C++14 (gcc 8.3)
created:
4 years 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!