Submission #780581

#	Time	Username	Problem	Language	Result	Execution time	Memory
780581		Minindu206	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	127 ms	138900 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
const int MAXN = 1e5 + 5;
using namespace std;
 
queue<int> pos[MAXN], neg[MAXN];
struct fenwick {
  int n;
  vector<int> fn;
  void init(int _n)
  {
    this->n = _n + 1;
    fn.resize(n, 0);
  }
  void update(int x, int y) 
  {
    x++;
    while(x < n)
    {
      fn[x] += y;
      x += (x & (-x));
    }
  }
  int sum(int ind)
  {
    ind++;
    int ans = 0;
    while(ind)
    {
      ans += fn[ind];
      ind -= (ind & (-ind));
    }
    return ans;
  }
};
 
ll count_swaps(vector<int> s)
{
    int n = s.size() / 2;
    for(int i=0;i<2 * n;i++)
    {
        if(s[i] > 0)
            pos[s[i]].push(i);
        else
            neg[-s[i]].push(i);
    } 
    vector<int> vis(2 * n);
    fenwick tree;
    tree.init((2 * n));
    ll ans = 0;
    for(int i=0;i<2*n;i++)
    {
        ll swps = 0;
        if(vis[i])
            continue;
        if(s[i] > 0)
        {
            int nxt = neg[s[i]].front();
            neg[s[i]].pop();
            pos[s[i]].pop();
            // cout << i << " " << nxt << '\n';
            // cout << "swaps " << (nxt - i) - (tree.sum(nxt + 1) - tree.sum(i + 1)) << '\n';
            ans += (nxt - i) - (tree.sum(nxt) - tree.sum(i));
            tree.update(nxt + 1, 1);
            vis[i] = 1;
            vis[nxt] = 1;
        }
        else
        {
            int nxt = pos[-s[i]].front();
            pos[-s[i]].pop();
            neg[-s[i]].pop();
            // cout << i << " " << nxt << '\n';
            // cout << "swaps " << (nxt - i - 1) - (tree.sum(nxt + 1) - tree.sum(i + 1)) << '\n';
            ans += (nxt - i - 1) - (tree.sum(nxt) - tree.sum(i));
            tree.update(nxt + 1, 1);
            vis[i] = 1;
            vis[nxt] = 1;
        }
    }
    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:54:12: warning: unused variable 'swps' [-Wunused-variable]
   54 |         ll swps = 0;
      |            ^~~~

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