Submission #891441

#	Time	Username	Problem	Language	Result	Execution time	Memory
891441		Muhammad_Aneeq	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	793 ms	164984 KiB

shoes

#include <set>
#include <vector>
#include <algorithm>
#include <map>
#include <deque>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
long long count_swaps(vector<int>s)
{
  int n=s.size()/2;
  map<int,deque<int>>d;
  for (int i=0;i<2*n;i++)
    d[s[i]].push_back(i);
  map<int,int>vis;
  ordered_set cur;
  long long ans=0;
  for (int i=0;i<2*n;i++)
  {
    if (vis[i])
      continue;
    int z=cur.order_of_key(d[-s[i]].front());
    z=d[-s[i]].front()-z-1;
    if (s[i]>0)
      ans+=z+1;
    else
      ans+=z;
    cur.insert(d[s[i]].front());
    cur.insert(d[-s[i]].front());
    vis[d[s[i]].front()]=vis[d[-s[i]].front()]=1;
    d[s[i]].pop_front();
    d[-s[i]].pop_front();
  }
  return ans;
}

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