Submission #257612

#	Time	Username	Problem	Language	Result	Execution time	Memory
257612		StevenH	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	104 ms	19816 KiB

shoes

// #include "shoes.h"
#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
int x, a[MAXN], n;
inline int lowbit(int x)
{
  return x & (-x);
}
void add(int x)
{
  while (x <= n)
  {
    a[x]++;
    x += lowbit(x);
  }
  return;
}
int pre(int x)
{
  int ans = 0;
  while (x > 0)
  {
    ans += a[x];
    x -= lowbit(x);
  }
  return ans;
}
int query(int x, int y)
{
  return pre(y) - pre(x - 1);
}
vector<vector<int> > rpos(MAXN), lpos(MAXN);
bool vis[MAXN];
long long count_swaps(std::vector<int> s)
{

  n = s.size();

  s.push_back(0);
  for (int i = n; i >= 1; i--)
    s[i] = s[i - 1];

  for (int i = n; i >= 1; i--)
    if (s[i] > 0)
      rpos[s[i]].push_back(i);
    else
      lpos[-s[i]].push_back(i);

  long long sum = 0;
  int cnt = 0;
  for (int i = 1; i <= n; i++)
  {
    if (vis[i])
      continue;
    if (s[i] < 0)
    {
      int ss = -s[i];
      sum += i + query(i + 1, n) - 1 - cnt;
      vis[i] = 1;
      add(i);
      int pos;
      for (pos = rpos[ss].back(); vis[pos] == 1; pos = rpos[ss].back())
        rpos[ss].pop_back();
      vis[pos] = 1;
      sum += pos - (cnt + 2) + query(pos + 1, n);
      add(pos);
      cnt += 2;
    }
    else if (s[i] > 0)
    {
      int ss = s[i];
      sum += (i - cnt - 1) + query(i + 1, n);
      add(i);
      vis[i] = 1;

      int pos;
      for (pos = lpos[ss].back(); vis[pos] == 1; pos = lpos[ss].back())
        lpos[ss].pop_back();
      vis[pos] = 1;
      sum += pos - (cnt + 2) + query(pos + 1, n) + 1;
      add(pos);
      cnt += 2;
    }
  }
  return sum;
}

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