Submission #776984

#	Time	Username	Problem	Language	Result	Execution time	Memory
776984		Trisanu_Das	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	186 ms	277956 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
ll n, BIT[100005];
queue<ll> l_unpair[100005], r_unpair[100005];
 
void upd(int idx, ll val){
  for(int i = idx; i < n + 1; i += (i & (-i))) BIT[i] += val;
}
 
ll qry(int idx){
  ll ans = 0;
  for(int i = idx; i > 0; i -= (i & (-i))) ans += BIT[i];
  return ans;
}
 
ll count_swaps(vector<int> s){
  n = s.size();
  ll swaps = 0;
  for(int i = 1; i < n + 1; i++){
    ll shoe_sz = s[i - 1];
    if(shoe_sz < 0){
      shoe_sz *= -1; // extracting shoe size;
      if(!r_unpair[shoe_sz].empty()){ //has a shoe unpaired of this(shoe_sz) size.
        ll shoe_need = r_unpair[shoe_sz].front(); r_unpair[shoe_sz].pop();
        swaps += qry(i) - qry(shoe_need - 1);
        upd(shoe_need, 1);
      }else{ // no shoe.
        l_unpair[shoe_sz].push(i); upd(i, 1);
      }
    }else{
      if(!l_unpair[shoe_sz].empty()){ //has a shoe unpaired of this(shoe_sz) size.
        ll shoe_need = l_unpair[shoe_sz].front(); l_unpair[shoe_sz].pop();
        swaps += qry(i) - qry(shoe_need);
        upd(shoe_need, 1);
      }else{ // no shoe.
        r_unpair[shoe_sz].push(i); upd(i, 1);
      }
    }
  }
  return swaps;
} 

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