Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Dec 7th, 2018 55 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. #include <bits/stdc++.h>
  2. #define err(...) fprintf(stderr, __VA_ARGS__), fprintf(stderr, "\n"), fflush(stderr)
  3.  
  4. typedef long long ll;
  5.  
  6. using namespace std;
  7.  
  8. #define TASK "braess"
  9.  
  10.  
  11. vector<vector<int>> T = { { 0, 1, 2, 3, 4, 5 },
  12.                   { 0, 3, 4, 2, 1, 5 },
  13.                   { 1, 5, 0, 2, 3, 4 },
  14.                   };
  15.  
  16. vector<vector<int>> Q = { { 0, 1, 2, 3, 4, 5, 6, 7, },
  17.                   { 0, 2, 4, 1, 3, 5, 6, 7 },
  18.                   { 0, 7, 6, 5, 3, 2, 1, 4 },
  19.                   };
  20.  
  21. vector<vector<int>> getG(vector<int> G) {
  22.     vector<vector<int>> T1(G.size());
  23.  
  24.     int n1 = (int)G.size() / 2;
  25.     for (int i = 0; i <= n1; i++) {
  26.         if (i > 0) T1[G[i]].push_back(G[i - 1]);
  27.         if (i < n1) T1[G[i]].push_back(G[i + 1]);
  28.         if (i > 0 && i < n1) T1[G[i]].push_back(G[i + n1]), T1[G[i + n1]].push_back(G[i]);
  29.     }
  30.     return T1;
  31. }
  32.  
  33. vector<vector<int>> del(vector<vector<int> > G, int a, int b) {
  34.     for (int i = 0; i < (int)G.size(); i++) {
  35.         for (int q = 0; q < (int)G[i].size(); q++) {
  36.             int j = G[i][q];
  37.             if (i == a && j == b || i == b && j == a) {
  38.                 G[i].erase(G[i].begin() + q);
  39.                 break;
  40.             }
  41.         }
  42.     }
  43.     return G;
  44. }
  45.  
  46.  
  47. vector<vector<int>> del(vector<vector<int> > G, int p) {
  48.     for (int i = 0; i < (int)G.size(); i++) if (i != p) {
  49.         for (int q = 0; q < (int)G[i].size(); q++) {
  50.             int j = G[i][q];
  51.             if (j == p) {
  52.                 G[i].erase(G[i].begin() + q);
  53.                 break;
  54.             }
  55.         }
  56.     }
  57.  
  58.     G.erase(G.begin() + p);
  59.  
  60.     for (int v = 0; v < (int)G.size(); v++) {
  61.         for (int &to : G[v]) {
  62.             if (to > p) to--;
  63.         }
  64.     }
  65.  
  66.     return G;
  67. }
  68.  
  69. vector<int> concat(vector<int> G, vector<int> A) {
  70.  
  71.     auto t1 = getG(G);
  72.     auto t2 = getG(A);
  73.  
  74.     vector<vector<int>> res(G.size() + A.size());
  75.  
  76.     for (int v = 0; v < (int)G.size(); v++) {
  77.         for (int to : t1[v]) {
  78.             res[v].push_back(to);
  79.         }
  80.     }
  81.     for (int v = 0; v < (int)A.size(); v++) {
  82.         for (int to : t2[v]) {
  83.             res[v + (int)G.size()].push_back(to + (int)G.size());
  84.         }
  85.     }
  86.  
  87.     res[G[G.size() / 2 - 1]].push_back((int)G.size() + A[1]);
  88.     res[(int)G.size() + A[1]].push_back(G[G.size() / 2 - 1]);
  89.  
  90.     res = del(res, G[G.size() / 2], G[G.size() / 2 - 1]);
  91.     res = del(res, (int)G.size() + A[0], (int)G.size() + A[1]);
  92.  
  93.     res = del(res, G[G.size() / 2]);
  94.     res = del(res, (int)G.size() + A[0]);
  95.  
  96.     for(int v = 0; v < (int)res.size(); v++) {
  97.         for (int to :res[v]) {
  98.             if ( v < to) err("%d--->%d",v, to);
  99.         }
  100.     }
  101.  
  102.  
  103.     int nxt = -1;
  104.     vector<int> used((int)res.size());
  105.     vector<int> num(res.size());
  106.     int cnt = 0;
  107.  
  108.     for (int v = 0; v < (int)res.size(); v = nxt) {
  109.  
  110.         vector<int> cur;
  111.         for (int to : res[v]) if (!used[to]) {
  112.             cur.push_back(to);
  113.         }
  114.  
  115.         num[v] = cnt++;
  116.         used[v] = 1;
  117.  
  118.         for (int x : cur) used[x] = 1;
  119.  
  120.         if (cur.empty()) break;
  121.  
  122.         if (cur.size() == 1) {
  123.             nxt = cur[0];
  124.         } else {
  125.             assert(cur.size() == 2);
  126.             if (res[cur[0]].size() == 1) nxt = cur[0];
  127.             else nxt = cur[1];
  128.  
  129.             for (int q = 0; q < (int)cur.size(); q++) {
  130.                 if (cur[q] != nxt) {
  131.                     num[cur[q]] = num[v] + (int) res.size() / 2;
  132.                 }
  133.             }
  134.         }
  135.     }
  136.     return num;
  137. }
  138.  
  139.  
  140. void solve() {
  141.     int n;
  142.     cin >> n;
  143.     for (int i = 0; i < 3; i++) {
  144.         vector<int> G = T[i];
  145.         if (n % 2 == 0) G = Q[i];
  146.         for (int j = 0; j < (n - 3) / 2; j++) {
  147.             G = concat(G, T[i]);
  148.         }
  149.         for (auto v : G) {
  150.             cout << v + 1 << ' ';
  151.         }
  152.         cout << '\n';
  153.     }
  154. }
  155.  
  156. int main() {
  157.     ios_base::sync_with_stdio(false);
  158.     cin.tie(nullptr);
  159. #ifdef SIR
  160.     freopen("input.txt", "r", stdin);
  161.     freopen("output.txt", "w", stdout);
  162. #else
  163.     freopen(TASK".in", "r", stdin);
  164.     freopen(TASK".out", "w", stdout);
  165. #endif
  166.     solve();
  167. }
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