Submission #1023309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023309		inesfi	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	249 ms	275060 KiB

shoes

#include<bits/stdc++.h>
using namespace std; 
 
const int MAXI = 200*1000 + 10;
queue<int> occ[2*MAXI]; 
bool dejaVu[MAXI]; 
 
const long long DECA = 1<<20; 
int arbre[2*DECA]; 
 
void modif(int pos){
  pos+=DECA; 
  arbre[pos] = 1; 
  while(pos>1){
    pos/=2; 
    arbre[pos] = arbre[2*pos] + arbre[2*pos+1]; 
  }
}
 
int calcSomme(int deb, int fin){
  if(deb==fin)
    return arbre[deb]; 
  if(deb%2==1)
    return arbre[deb] + calcSomme(deb+1, fin); 
  if(fin%2==0)
    return calcSomme(deb, fin-1) + arbre[fin]; 
  return calcSomme(deb/2, fin/2); 
}
 
 
long long count_swaps(vector<signed> s) {
  int nb = s.size(); 
  for(int c=0; c<nb; c++){
    occ[MAXI + s[c]].push(c); 
  }
  long long res = 0; 
  for(int g=0; g<nb; g++){
    if(!dejaVu[g]){
      int d = occ[MAXI - s[g]].front(); 
      occ[MAXI - s[g]].pop(); 
      occ[MAXI + s[g]].pop(); 
      dejaVu[d] = true; 
      if(s[g] < 0){    // si chaussure gauche
        res += d-g-1; 
      }
      else{ // si chaussure droite
        res+= d-g; 
      }
      res -= calcSomme(g+DECA, d+DECA);
      modif(d); 
    }
  }
 
  return res;
}

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