fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define taskname "llist"
  5.  
  6. int main() {
  7.   if (fopen(taskname".inp", "r")) {
  8.     freopen(taskname".inp", "r", stdin);
  9.     freopen(taskname".out", "w", stdout);
  10.   }
  11.  
  12.   cin.tie(0)->sync_with_stdio(0);
  13.  
  14.   int n, m; cin >> n >> m;
  15.   vector<int> L(n + 2), R(n + 2);
  16.   for (int i = 1; i <= n; i++) {
  17.     L[i] = i - 1;
  18.     R[i] = i + 1;
  19.   }
  20.   function<void(int, int, int)> modify = [&](int e, int x, int y) {
  21.     R[L[x]] = R[x];
  22.     L[R[x]] = L[x];
  23.     if (!e) {
  24.       R[L[y]] = x;
  25.       L[x] = L[y];
  26.       R[x] = y;
  27.       L[y] = x;
  28.     }
  29.     else {
  30.       L[R[y]] = x;
  31.       R[x] = R[y];
  32.       L[x] = y;
  33.       R[y] = x;
  34.     }
  35.   };
  36.   for (int i = 0; i < m; i++) {
  37.     char c; int x, y;
  38.     cin >> c >> x >> y;
  39.     modify(c - 'A', x, y);
  40.   }
  41.  
  42.   vector<int> a;
  43.   for (int i = 1; i <= n; i++) {
  44.     if (L[i] == 0) {
  45.       a.push_back(i);
  46.       break;
  47.     }
  48.   }
  49.   while (R[a.back()] != n + 1) {
  50.     a.push_back(R[a.back()]);
  51.   }
  52.  
  53.   vector<int> b, f(n);
  54.   for (int i = 0; i < n; i++) {
  55.     f[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
  56.     if (f[i] >= b.size()) {
  57.       b.push_back(0);
  58.     }
  59.     b[f[i]] = a[i];
  60.   }
  61.  
  62.   int x = b.size();
  63.   vector<int> c;
  64.   for (int i = n - 1; ~i; i--) {
  65.     if (f[i] == x - 1) {
  66.       c.push_back(a[i]);
  67.       x--;
  68.     }
  69.   }
  70.   c.push_back(0);
  71.   reverse(c.begin(), c.end());
  72.   vector<array<int, 3>> ans;
  73.   for (int i = 0; i < c.size() - 1; i++) {
  74.     for (int j = c[i + 1] - 1; j > c[i]; j--) {
  75.       ans.push_back({0, j, j + 1});
  76.     }
  77.   }
  78.   for (int j = c.back() + 1; j <= n; j++) {
  79.     ans.push_back({1, j, j - 1});
  80.   }
  81.  
  82.   cout << ans.size() << "\n";
  83.   for (auto &x: ans) {
  84.     cout << (x[0] ? 'B': 'A') << " " << x[1] << " " << x[2] << "\n";
  85.   }
  86.  
  87.   return 0;
  88. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/L4hsnz
language:
C++14 (gcc 8.3)
created:
2 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!