Submission #1110426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110426		SonicML	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	210 ms	19096 KiB

shoes

#include <iostream>
#include "shoes.h"
#include <map>

using namespace std;

int const NMAX = 2e5;
int freq[1 + NMAX];
map <pair <int, int>, int> pos;
pair <int, int> arr[1 + NMAX];
bool vis[1 + NMAX];
int aib[1 + NMAX];

void update(int pos, int add, int n) {
  for(int i = pos;i <= n;i = 2 * i - (i&(i-1))) {
    aib[i] += add;
  }
}

int query(int pos) {
  int ans = 0;
  for(int i = pos;i > 0;i = (i&(i-1))) {
    ans += aib[i];
  } 
  return ans;
}

long long count_swaps(vector <int> s) {
  int n = s.size(), nn = s.size()/2;
  for(int i = 0;i < n;i++) {
    freq[s[i]+nn]++;
    arr[i] = {s[i], freq[s[i]+nn]};
    pos[arr[i]] = i;
    update(i+1, 1, n);
  }
  long long ans = 0;
  for(int i = 0;i < n;i++) {
    if(!vis[i]) {
      pair <int, int> partner = {-arr[i].first, arr[i].second};
      int to = max(pos[partner], i), from = min(pos[partner], i);
      int dist = query(to+1) - query(from+1);  
      if(s[i] < 0) {
	dist--;
      }
      ans += dist;
      vis[i] = vis[pos[partner]] = true;
      update(i+1, -1, n);
      update(pos[partner]+1, -1, n);
    }
  }
  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