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. /*
  41. int power(int x, unsigned int y, unsigned int M)
  42. {
  43.     if (y == 0)
  44.         return 1;
  45.  
  46.     int p = power(x, y / 2, M) % M;
  47.     p = (p * p) % M;
  48.  
  49.     return (y % 2 == 0) ? p : (x * p) % M;
  50. }*/
  51.  
  52. void setIO(string name = "")
  53. {
  54.     cin.tie(0)->sync_with_stdio(0);
  55.     if (sz(name))
  56.     {
  57.         freopen((name + ".in").c_str(), "r", stdin);
  58.         freopen((name + ".out").c_str(), "w", stdout);
  59.     }
  60. }
  61.  
  62. ll t, x, m, k, q, n;
  63.  
  64. void solve()
  65. {
  66.     cin >> n;
  67.     unordered_map<int, int> mov;
  68.     unordered_map<int, int> box;
  69.     box.reserve(n + 5);
  70.     mov.reserve(n + 5);
  71.     vii stuff(n);
  72.     for (int i = 0; i < n; i++)
  73.     {
  74.         // box movie
  75.         cin >> stuff[i].ff >> stuff[i].ss;
  76.         stuff[i].ff--, stuff[i].ss--;
  77.         box[stuff[i].ff] = stuff[i].ss; // en esta caja esta esta peli
  78.         mov[stuff[i].ss] = stuff[i].ff; // esta peli en esta caja
  79.     }
  80.     ll algo2 = 0;
  81.  
  82.     for (int i = 0; i < n - 1; i++)
  83.     {
  84.         algo2++;
  85.         while (i != box[i])
  86.         {
  87.             int j = box[i];
  88.             algo2 += abs(i - j);
  89.             swap(box[i], box[j]);
  90.             i = box[i];
  91.             algo2 += abs(i - j);
  92.         }
  93.     }
  94.  
  95.     for (int i = 0; i < n; i++)
  96.     {
  97.         box[stuff[i].ff] = stuff[i].ss; // en caja i esta esta peli
  98.     }
  99.     ll algo1 = 0;
  100.     for (int i = 0; i < n - 1; i++)
  101.     {
  102.         algo1++;
  103.         if (mov[i] != box[i])
  104.         {
  105.             algo1 += abs(i - box[i]) * 2;
  106.             swap(mov[box[i]], mov[box[box[i]]]);
  107.             continue;
  108.         }
  109.     }
  110.  
  111.     cout << algo1 << " " << algo2 << nl;
  112. }
  113.  
  114. signed main()
  115. {
  116.     setIO();
  117.     int tc = 1;
  118.     // cin >> tc;
  119.     while (tc--)
  120.         solve();
  121.     return 0;
  122. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/zM103j
language:
C++14 (gcc 8.3)
created:
7 days 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!