SHARE
TWEET

Untitled

lalalalalalalaalalla Sep 23rd, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <iomanip>
  5. #include <queue>
  6. #include <cmath>
  7. #include <algorithm>
  8. #include <tuple>
  9. #include <iomanip>
  10. #include <stdio.h>
  11. #include <numeric>
  12. #include <map>
  13. #include <bitset>
  14. #include <set>
  15. #include <stack>
  16. #include <queue>
  17.  
  18. /*
  19. #pragma GCC optimize("Ofast,no-stack-protector")
  20. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
  21. #pragma GCC optimize("unroll-loops")
  22. #pragma GCC optimize("fast-math")
  23. #pragma GCC optimize("section-anchors")
  24. #pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
  25. #pragma GCC optimize("vpt")
  26. #pragma GCC optimize("rename-registers")
  27. #pragma GCC optimize("move-loop-invariants")
  28. #pragma GCC optimize("unswitch-loops")
  29. #pragma GCC optimize("function-sections")
  30. #pragma GCC optimize("data-sections")
  31. #pragma GCC optimize("branch-target-load-optimize")
  32. #pragma GCC optimize("branch-target-load-optimize2")
  33. #pragma GCC optimize("btr-bb-exclusive")
  34. */
  35.  
  36. #define int long long
  37. #define ll long long
  38. #define ull unsigned long long
  39. #define all(a) a.begin(), a.end()
  40. #define pii pair<int, int>
  41. #define pb push_back
  42. #define ld long double
  43.  
  44.  
  45. using namespace std;
  46.  
  47. const int INF = 1e13;
  48. //const int mod = 2600000069;
  49. //const int p = 179;
  50.  
  51. int n, m;
  52. vector<vector<pii>> g;
  53. vector<int> pos;
  54. vector<int> p;
  55. vector<bool> ban;
  56. pii u;
  57.  
  58. void euler(int v) {
  59.     stack<int> s;
  60.     s.push(v);
  61.     while (!s.empty()) {
  62.         v = s.top();
  63.         while (pos[v] != g[v].size() && ban[g[v][pos[v]].second]) {
  64.             pos[v]++;
  65.         }
  66.         if (pos[v] == g[v].size()) {
  67.             p.pb(v);
  68.             s.pop();
  69.             continue;
  70.         }
  71.         u = g[v][pos[v]];
  72.         ban[u.second] = 1;
  73.         s.push(u.first);
  74.         pos[v]++;
  75.     }
  76. }
  77.  
  78. signed main() {
  79.     ios_base::sync_with_stdio(0);
  80.     cin.tie(0);
  81.     cout.tie(0);
  82.     cin >> n >> m;
  83.     g.resize(2 * n + 2);
  84.     pos.assign(2 * n + 2, 0);
  85.     vector<pii> c;
  86.     c.resize(m);
  87.     int ind = 0;
  88.     vector<bool> used1(n, 0), used2(n, 0);
  89.     for (int i = 0; i < m; i++) {
  90.         cin >> c[i].first >> c[i].second;
  91.         c[i].first--;
  92.         c[i].second--;
  93.         g[c[i].first].pb({n + c[i].second, ind});
  94.         g[n + c[i].second].pb({c[i].first, ind});
  95.         ind++;
  96.         if (!used1[c[i].first]) {
  97.             g[c[i].first].pb({2 * n, ind});
  98.             g[2 * n].pb({c[i].first, ind});
  99.             ind++;
  100.         }
  101.         if (!used2[c[i].second]) {
  102.             g[c[i].second].pb({2 * n + 1, ind});
  103.             g[2 * n + 1].pb({c[i].second, ind});
  104.             ind++;
  105.         }
  106.     }
  107.     ban.assign(ind, 0);
  108.     int start = -1;
  109.     for (int i = 0; i < 2 * n + 2; i++) {
  110.         if (g[i].size() % 2) {start = i; continue;}
  111.         if (start == -1 && g[i].size()) start = i;
  112.     }
  113.     euler(start);
  114.     int ps = p.size();
  115.     map<pii, string> ans;
  116.     bool color = 0;
  117.     cout << ps << "\n";
  118.     for (int i = 0; i < ps - 1; i++) {
  119.         if (p[i] >= 2 * n || p[i + 1] >= 2 * n) continue;
  120.         if (p[i + 1] >= n) {
  121.             ans[{p[i], p[i + 1] - n}] = (color ? "M" : "W");
  122.             cout << "first: " << p[i] << " " << p[i + 1] - n << "\n";
  123.         }
  124.         if (p[i] >= n) {
  125.             ans[{p[i + 1], p[i] - n}] = (color ? "M" : "W");
  126.             cout << "second: " << p[i] - n << " " << p[i + 1] << "\n";
  127.         }
  128.         color = !color;
  129.     }
  130.     if (p[ps - 1] >= n) {
  131.         ans[{p[0], p[ps - 1] - n}] = (color ? "M" : "W");
  132.         cout << p[0] << " " << p[ps - 1] << "\n";
  133.     }
  134.     if (p[0] >= n) {
  135.         ans[{p[ps - 1], p[0] - n}] = (color ? "M" : "W");
  136.         cout << p[ps - 1] << " " << p[0] - n << "\n";
  137.     }
  138.     if (p[0] >= n && p[ps - 1] >= n) {
  139.         ans[{p[ps - 1], p[0]}]
  140.     }
  141.     cout << "\n";
  142.     for (auto k: c) {
  143.         cout << k.first << " " << k.second << "\n";
  144.         cout << ans[k];
  145.     }
  146. }
  147. /*
  148.  2 2
  149.  2 1
  150.  1 2
  151. */
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