Submission #257607

#	Time	Username	Problem	Language	Result	Execution time	Memory
257607		StevenH	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1096 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 = 1; i <= n; 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;
      //cout<<sum<<" ";
      add(i);
      for (int j = 0; j < (int)rpos[ss].size(); j++)
      {
        int pos = rpos[ss][j];
        if (vis[pos])
          continue;
        vis[pos] = 1;
        //cout<<i<<" "<<pos<<endl;
        sum += pos - (cnt + 2) + query(pos + 1, n);
        add(pos);
        //cout<<sum<<endl;
        break;
      }
      cnt += 2;
    }
    else if (s[i] > 0)
    {
      int ss = s[i];
      sum += (i - cnt - 1) + query(i + 1, n);
      add(i);
      vis[i] = 1;
      for (int j = 0; j < (int)lpos[ss].size(); j++)
      {
        int pos = lpos[ss][j];
        if (vis[pos])
          continue;
        vis[pos] = 1;
        sum += pos - (cnt + 2) + query(pos + 1, n) + 1;
        add(pos);
        break;
      }
      cnt += 2;
    }
  }
  return sum;
}

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