Advertisement
Guest User

Untitled

a guest
Oct 15th, 2019
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.25 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using uint = unsigned int;
  4. using ll = long long;
  5. using ull = unsigned long long;
  6. using pii = pair<int, int>;
  7. using pll = pair<ll, ll>;
  8. #define dbg(x) cerr<<#x": "<<(x)<<endl
  9. #define dbg_p(x) cerr<<#x": "<<(x).first<<' '<<(x).second<<endl
  10. #define dbg_v(x, n) {cerr<<#x"[]: ";for(long long _=0;_<n;++_)cerr<<(x)[_]<<' ';cerr<<endl;}
  11. #define all(v) v.begin(), v.end()
  12. #define fi first
  13. #define se second
  14.  
  15. template<typename T1, typename T2>
  16. ostream& operator <<(ostream &out, const pair<T1, T2> &item) {
  17. out << '(' << item.first << ", " << item.second << ')';
  18. return out;
  19. }
  20.  
  21. template <typename T>
  22. ostream& operator <<(ostream &out, const vector<T>& v) {
  23. for(const auto &item : v) out << item << ' ';
  24. return out;
  25. }
  26.  
  27. int p[222], n;
  28.  
  29. set <int> v[222];
  30.  
  31. int nr = 1;
  32.  
  33. void add_edge(int a, int b) {
  34. if(v[a].count(b) || v[b].count(a)) {
  35. cerr << "Error!" << nr << ' ' << a << ' ' << b << '\n';
  36. exit(-1);
  37. }
  38. v[a].insert(b);
  39. v[b].insert(a);
  40. }
  41.  
  42. void add_edges() {
  43. // v[p[1]].insert(p[2]]);
  44. // v[p[n + 1]].insert(p[n]);
  45.  
  46. for(int i = 2; i <= n; i++) {
  47. add_edge(p[i], p[i - 1]);
  48. add_edge(p[i], p[n + i - 1]);
  49. }
  50. add_edge(p[n], p[n + 1]);
  51. }
  52.  
  53. int main()
  54. {
  55. ios_base::sync_with_stdio(false);
  56.  
  57. ifstream fin("embedding.in");
  58.  
  59. fin >> n;
  60.  
  61.  
  62. for(int i = 1; i <= 2 * n; i++) cin >> p[i];
  63. add_edges();
  64. for(int i = 1; i <= 2 * n; i++) cin >> p[i];
  65. nr++;
  66. add_edges();
  67. for(int i = 1; i <= 2 * n; i++) cin >> p[i];
  68. nr++;
  69. add_edges();
  70.  
  71. return 0;
  72. }
  73.  
  74.  
  75.  
  76. /*
  77.  
  78. cristi@pop-os:~/contest$ ./check <embedding.out
  79. Error!2 8 3
  80. cristi@pop-os:~/contest$ cat embedding.out
  81. 1 2 3 4 5 6 7 8 9 10 11 12
  82. 1 7 8 9 10 11 12 3 4 5 6 2
  83. 1 6 4 2 5 3 12 7 10 8 11 9
  84. cristi@pop-os:~/contest$
  85.  
  86.  
  87. */
  88.  
  89.  
  90.  
  91. #include <bits/stdc++.h>
  92. using namespace std;
  93. using uint = unsigned int;
  94. using ll = long long;
  95. using ull = unsigned long long;
  96. using pii = pair<int, int>;
  97. using pll = pair<ll, ll>;
  98. #define dbg(x) cerr<<#x": "<<(x)<<endl
  99. #define dbg_p(x) cerr<<#x": "<<(x).first<<' '<<(x).second<<endl
  100. #define dbg_v(x, n) {cerr<<#x"[]: ";for(long long _=0;_<n;++_)cerr<<(x)[_]<<' ';cerr<<endl;}
  101. #define all(v) v.begin(), v.end()
  102. #define fi first
  103. #define se second
  104.  
  105. template<typename T1, typename T2>
  106. ostream& operator <<(ostream &out, const pair<T1, T2> &item) {
  107. out << '(' << item.first << ", " << item.second << ')';
  108. return out;
  109. }
  110.  
  111. template <typename T>
  112. ostream& operator <<(ostream &out, const vector<T>& v) {
  113. for(const auto &item : v) out << item << ' ';
  114. return out;
  115. }
  116.  
  117. const int N = 110;
  118. int n, p1[N], p2[N], p3[N];
  119. set <int> v[N];
  120.  
  121. void first(int * p) {
  122. // v[1].insert(2);
  123. // v[n + 1].insert(n);
  124.  
  125. // for(int i = 2; i <= n; i++) {
  126. // v[i].insert(i - 1);
  127. // v[i].insert(i + 1);
  128. // v[i].insert(n + i);
  129. // v[n + i].insert(i);
  130. // }
  131.  
  132. for(int i = 1; i <= 2 * n; i++) p[i] = i;
  133. }
  134.  
  135. void second(int * p) {
  136. p[1] = 1;
  137. p[n + 1] = 2 * n;
  138. for(int i = 2; i <= 2 * n; i++) {
  139. if(i >= 2 && i <= n) p[i] = n + i - 1;
  140. else if(i == 2 * n) p[i] = 2;
  141. else if(i != n + 1) p[i] = i - n + 1;
  142. }
  143. }
  144.  
  145. void third(int * p) {
  146. p[1] = 1;
  147. p[n + 1] = 2 * n;
  148.  
  149. vector <int> v[2], g, g2;
  150. for(int i = 2; i <= n; i++)
  151. v[i % 2].push_back(i);
  152.  
  153. int pp[N];
  154. for(int i = 2; i <= n; i++)
  155. pp[i] = n + i - 1;
  156.  
  157. dbg_v(pp, n + 1);
  158. rotate(pp + 2, pp + 3, pp + n + 1);
  159. dbg_v(pp, n + 1);
  160.  
  161. for(auto i : v[1]) g.push_back(i), g2.push_back(pp[i]);
  162. for(auto i : v[0]) g.push_back(i), g2.push_back(pp[i]);
  163.  
  164. // dbg(g2);
  165. // rotate(g2.begin(), g2.begin() + 2, g2.end());
  166. dbg(g);
  167. dbg(g2);
  168.  
  169. for(int i = 2; i <= 2 * n; i++) {
  170. if(i <= n) p[i] = g.back(), g.pop_back();
  171. else if(i != n + 1) p[i] = g2.back(), g2.pop_back();
  172. }
  173. }
  174.  
  175. void solve(int n) {
  176. // for(int i = 1; i <= n; i++)
  177. // v[i].clear();
  178.  
  179. if(n >= 5) {
  180. first(p1);
  181. second(p2);
  182. third(p3);
  183. } else if(n == 3) {
  184.  
  185. } else if(n == 4) {
  186.  
  187. }
  188.  
  189. for(int i = 1; i <= 2 * n; i++) cout << p1[i] << " \n"[i == 2 * n];
  190. for(int i = 1; i <= 2 * n; i++) cout << p2[i] << " \n"[i == 2 * n];
  191. for(int i = 1; i <= 2 * n; i++) cout << p3[i] << " \n"[i == 2 * n];
  192.  
  193. }
  194.  
  195. int main()
  196. {
  197. ios_base::sync_with_stdio(false);
  198.  
  199.  
  200. cin >> n;
  201. while(n) {
  202.  
  203. solve(n);
  204.  
  205. cin >> n;
  206. }
  207.  
  208. return 0;
  209. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement