Submission #1015448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015448		nam6	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	591 ms	1048576 KiB

shoes

    #include<bits/stdc++.h>
    using namespace std; 
    #define int long long
     
    const int MAXI = 100*1000 + 10;
    queue<int> occ[2*MAXI]; 
    bool dejaVu[MAXI]; 
     
    const int 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();
      //cout << nb << endl; 
      for(int c=0; c<nb; c++){
        //cout << s[c] << endl;
        occ[MAXI + s[c]].push(c); 
      }
      int 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: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15