SHARE
TWEET

Untitled

a guest Oct 15th, 2019 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top