fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. using ll = long long;
  5. using ull = unsigned long long;
  6.  
  7. using ii = pair<int, int>;
  8. using vi = vector<int>;
  9. using vll = vector<ll>;
  10. using vii = vector<ii>;
  11.  
  12. const int mod = 1e9 + 7;
  13. #define nl '\n'
  14. #define ff first
  15. #define ss second
  16. #define pb push_back
  17. #define sz(x) (int)x.size()
  18. #define all(x) x.begin(), x.end()
  19.  
  20. #define debug(x)          \
  21.     for (auto &e : x)     \
  22.         cout << e << " "; \
  23.     cout << nl;
  24.  
  25. #define yes cout << "Yes" << nl;
  26. #define no cout << "No" << nl;
  27.  
  28. int gcd(int a, int b)
  29. {
  30.     if (b == 0)
  31.         return a;
  32.     else
  33.         return gcd(b, a % b);
  34. }
  35. int lcm(int a, int b)
  36. {
  37.     return a * b / gcd(a, b);
  38. }
  39.  
  40. void setIO(string name = "")
  41. {
  42.     cin.tie(0)->sync_with_stdio(0);
  43.     if (sz(name))
  44.     {
  45.         freopen((name + ".in").c_str(), "r", stdin);
  46.         freopen((name + ".out").c_str(), "w", stdout);
  47.     }
  48. }
  49. ll t, x, m, k, q, n;
  50.  
  51. ll algoritmo2(unordered_map<int, int> where_box, vi boxes, vi movies)
  52. {
  53.     ll algo2 = 0;
  54.     for (int i = 0; i < n - 1; i++)
  55.     {
  56.         algo2++;
  57.         int now = i;
  58.         while (movies[i] != boxes[i])
  59.         {
  60.             int j = where_box[movies[i]];
  61.  
  62.             algo2 += abs(now - j);
  63.             swap(movies[i], movies[j]);
  64.             now = j;
  65.         }
  66.         // regreso
  67.         algo2 += abs(i - now);
  68.         // si es igual + 0
  69.     }
  70.     return algo2;
  71. }
  72.  
  73. ll algoritmo1(unordered_map<int, int> where_box, vi boxes, vi movies)
  74. {
  75.     ll algo1 = 0;
  76.     for (int i = 0; i < n - 1; i++)
  77.     {
  78.         algo1++;
  79.         if (movies[i] != boxes[i])
  80.         {
  81.             int j = where_box[movies[i]];
  82.             algo1 += abs(i - j) * 2;
  83.             swap(boxes[i], boxes[j]);
  84.             swap(where_box[boxes[i]], where_box[boxes[j]]);
  85.         }
  86.     }
  87.     return algo1;
  88. }
  89.  
  90. void solve()
  91. {
  92.     cin >> n;
  93.     unordered_map<int, int> where_mov;
  94.     unordered_map<int, int> where_box;
  95.     where_mov.reserve(n + 5);
  96.     where_box.reserve(n + 5);
  97.     vi movies(n);
  98.     vi boxes(n);
  99.     for (int i = 0; i < n; i++)
  100.     {
  101.         cin >> boxes[i] >> movies[i];
  102.         boxes[i]--, movies[i]--;
  103.         where_box[boxes[i]] = i;  // aqui esta la caja
  104.         where_mov[movies[i]] = i; // aqui esta la peli
  105.     }
  106.  
  107.     cout << algoritmo1(where_box, boxes, movies) << " " << algoritmo2(where_box, boxes, movies) << nl;
  108. }
  109.  
  110. signed main()
  111. {
  112.     setIO();
  113.     int tc = 1;
  114.     // cin >> tc;
  115.     while (tc--)
  116.         solve();
  117.     return 0;
  118. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
4
1 3
2 1
3 2
4 4
stdout
copy 
9 7
https://ideone.com/vo8GYU
language:
C++14 (gcc 8.3)
created:
20 hours 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!