Submission #1036814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036814		cjoa	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	404 ms	151320 KiB

shoes

#include "shoes.h"
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <cassert>

using namespace std;

struct SegmentTree {
   int N;
   vector<int> tree;
   SegmentTree(int _N) : N(_N), tree(4*_N) {
   }
   int query(int p, int q, int id, int L, int R) {
      if (L > q or R < p)
         return 0;
      if (p <= L and R <= q)
         return tree[id];
      int mid = (L + R) / 2;
      return query(p, q, 2*id, L, mid) + query(p, q, 2*id+1, mid+1, R);
   }
   int query(int p, int q) {
      return query(p, q, 1, 0, N-1);
   }
   void increase(int p, int val, int id, int L, int R) {
      if (p < L or p > R)
         return;
      if (L == R) {
         tree[id] += val;
         return;
      }
      int mid = (L + R) / 2;
      increase(p, val, 2*id, L, mid);
      increase(p, val, 2*id+1, mid+1, R);
      tree[id] = tree[2*id] + tree[2*id+1];
   }
   void increase(int p, int val) {
      increase(p, val, 1, 0, N-1);
   }
};

long long count_swaps(std::vector<int> s) {
   vector< pair<int,int> > parejas;
   map<int,queue<int> > last;
   for (int i = int(s.size())-1; i >= 0; --i) {
      int x = s[i];
      if (!last[-x].empty()) {
         parejas.emplace_back(i, last[-x].front());
         last[-x].pop();
      }
      else
         last[x].push(i);
   }

   reverse(parejas.begin(), parejas.end());
   
   long long ret = 0;

   SegmentTree st(s.size());
   for (auto p : parejas) {
      int l, r;
      tie(l, r) = p;
      int steps = r - l - 1 - st.query(l+1, r-1);
      if (s[l] > 0) {
         ++steps;
      }
   //   cerr << l << ' ' << r << ' ' << steps << endl;
      ret += steps;
      st.increase(r, 1);
   }

	return ret;


/*
   // subtask 5
   long long ret = 0;
   for (int i = 0; i < int(s.size()); i += 2) {
      int j;
      for (j = i+1; j < int(s.size()); j++) {
         if (s[j] == -s[i])
            break;
      }
      assert( j < int(s.size()) );
      int steps = 0;
      for (; j > i+1; --j) {
         swap(s[j], s[j-1]);
         ++steps;
      }
      if (s[j] < 0) {
         swap(s[j], s[i]);
         ++steps;
      }
      ret += steps;
   }
   return ret;
*/

}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15