fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair < int, int > ii;
  7.  
  8. const int N = 300 + 5;
  9.  
  10. int n;
  11. int ds[N][N];
  12. vector < pair < ii, ii > > ans;
  13.  
  14. void add3(int a, int b, int c) {
  15. 	ans.push_back({{a, b}, {c, 0}});
  16. 	// printf("3 %d %d %d\n", a, b, c);
  17. 	ds[a][b]++;
  18. 	ds[b][c]++;
  19. 	ds[c][a]++;
  20. }
  21.  
  22. void add4(int a, int b, int c, int d) {
  23. 	ans.push_back({{a, b}, {c, d}});
  24. 	// printf("4 %d %d %d %d\n", a, b, c, d);
  25. 	ds[a][b]++;
  26. 	ds[b][c]++;
  27. 	ds[c][d]++;
  28. 	ds[d][a]++;
  29. }
  30.  
  31. void check() {
  32. 	printf("%d\n", ans.size());
  33. 	for(auto x : ans) {
  34. 		printf("%d", x.second.second ? 4 : 3);
  35. 		printf(" %d %d %d", x.first.first, x.first.second, x.second.first);
  36. 		if(x.second.second)
  37. 			printf(" %d", x.second.second);
  38. 		puts("");
  39. 	}
  40. 	for(int i = 1; i <= n; i++) {
  41. 		for(int j = i + 1; j <= n; j++) {
  42. 			int d = ds[i][j] + ds[j][i];
  43. 			if(d != 2) {
  44. 				printf("i = %d j = %d d = %d\n", i, j, d);
  45. 				puts("ERROR!");
  46. 				assert(0);
  47. 			}
  48. 		}
  49. 	}
  50. }
  51.  
  52. void solve(vector < int > v) {
  53. 	if(v.size() <= 1)
  54. 		return;
  55. 	if(v.size() == 2) {
  56. 		//impossible
  57. 		puts("BRUH?");
  58. 		return;
  59. 	}
  60. 	if(v.size() == 3) {
  61. 		add3(v[0], v[1], v[2]);
  62. 		add3(v[0], v[1], v[2]);
  63. 		return;
  64. 	}
  65. 	if(v.size() == 4) {
  66. 		add4(v[0], v[1], v[2], v[3]);
  67. 		add4(v[0], v[1], v[3], v[2]);
  68. 		add4(v[0], v[2], v[1], v[3]);
  69. 		return;
  70. 	}
  71. 	if(v.size() == 5) {
  72. 		add3(v[4], v[3], v[1]);
  73. 		add3(v[2], v[0], v[4]);
  74. 		add4(v[3], v[4], v[1], v[2]);
  75. 		add4(v[3], v[2], v[1], v[0]);
  76. 		add3(v[3], v[1], v[0]);
  77. 		add3(v[2], v[0], v[4]);
  78. 		return;
  79. 		// 3 5 4 2
  80. 		// 3 3 1 5
  81. 		// 4 4 5 2 3
  82. 		// 4 4 3 2 1
  83. 		// 3 4 2 1
  84. 		// 3 3 1 5
  85. 	}
  86. 	if(v.size() == 6) {
  87. 		add3(v[0], v[1], v[2]);
  88. 		add3(v[0], v[1], v[2]);
  89. 		add3(v[0], v[3], v[4]);
  90. 		add3(v[0], v[3], v[5]);
  91. 		add3(v[0], v[4], v[5]);
  92. 		add3(v[1], v[3], v[4]);
  93. 		add4(v[1], v[3], v[2], v[5]);
  94. 		add4(v[1], v[4], v[2], v[5]);
  95. 		add4(v[2], v[3], v[5], v[4]);
  96. 		return;
  97. 	}
  98. 	if(n % 2 == 0) {
  99. 		int a = v.back(); v.pop_back();
  100. 		int b = v.back(); v.pop_back();
  101. 		int c = v.back(); v.pop_back();
  102. 		int d = v.back(); v.pop_back();
  103. 		solve(v);
  104. 		for(int i = 0; i + 1 < v.size(); i += 2) {
  105. 			int x = v[i], y = v[i + 1];
  106. 			add4(a, x, b, y);
  107. 			add4(a, x, b, y);
  108. 			add4(c, x, d, y);
  109. 			add4(c, x, d, y);
  110. 		}
  111. 		vector < int > v2 = {a, b, c, d};
  112. 		solve(v2);
  113. 		return;
  114. 	}
  115. 	int a = v.back(); v.pop_back();
  116. 	int b = v.back(); v.pop_back();
  117. 	solve(v);
  118. 	for(int i = 0; i + 1 < v.size(); i += 2) {
  119. 		int x = v[i], y = v[i + 1];
  120. 		add4(a, x, b, y);
  121. 		add4(a, x, b, y);
  122. 	}
  123. 	vector < int > v2 = {a, b, v.back()};
  124. 	solve(v2);
  125. }
  126.  
  127. int main() {
  128.  
  129. 	scanf("%d", &n);
  130.  
  131. 	vector < int > v;
  132.  
  133. 	for(int i = 1; i <= n; i++)
  134. 		v.push_back(i);
  135.  
  136. 	solve(v);
  137.  
  138. 	check();
  139.  
  140.     return 0;
  141.  
  142. }
  143.  
  144.  
Success #stdin #stdout 0s 15600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/zzLnUp
language:
C++14 (gcc 8.3)
created:
7 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!