Submission #802420

#	Time	Username	Problem	Language	Result	Execution time	Memory
802420		Benmath	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	85 ms	17672 KiB

shoes

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/
#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

int tree[800001];
void update(int node,int start,int end,int idx,int val){
    if(start==end){
        tree[node]+=val;
    }else{
        int mid=(start+end)/2;
        if(start<=idx and idx<=mid){
            update(2*node,start,mid,idx,val);
        }else{
            update(2*node+1,mid+1,end,idx,val);
        }
        tree[node]=tree[2*node]+tree[2*node+1];
    }
}
int query(int node,int start,int end,int l,int r){
    if(l<=start and end<=r){
        return tree[node];
    }
    if(r<start or end<l){
        return 0;
    }
    int mid=(start+end)/2;
    return query(2*node,start,mid,l,r)+query(2*node+1,mid+1,end,l,r);
}
long long count_swaps(std::vector<int> s) {
int n=s.size();
n=n/2;

   int ropos[n+1];
   int roneg[n+1];
   int vis[2*n+1];
   vector<int>vpos[n+1];
   vector<int>vneg[n+1];
   for(int i=0;i<=n;i++){
       ropos[i]=0;
       roneg[i]=0;
   }
   for(int i=0;i<2*n;i++){
   vis[i]=0;
       if(s[i]>0){
           vpos[s[i]].push_back(i);
       }else{
           vneg[abs(s[i])].push_back(i);
       }
   }
   long long int sum=0;
   int indeks=0;
   for(int i=0;i<2*n;i=i+2){
   	while(vis[indeks]>0){
   		indeks++;
	   }
      int x1=indeks;
      indeks++;
      while(vis[indeks]>0){
      	indeks++;
	  }
   int x2=indeks;
       int tren1=s[x1];
       int tren2=s[x2];
       if((tren1+tren2)!=0){
           int ind;
           if(tren1>0){
               ind=vneg[tren1][roneg[tren1]];
              
           }else{
               ind=vpos[abs(tren1)][ropos[abs(tren1)]];
              
           }    int ind1=ind;
           if(ind1!=(2*n-1)){
           
               ind=ind1+query(1,0,2*n-1,ind1+1,2*n-1);
           }
           
           sum=sum+(ind-(i+1));
           vis[ind1]++;
           vis[x1]++;
           update(1,0,2*n-1,ind1,1); 
        // cout<<sum<<" "<<tren1<<" "<<ind<<" "<<ind1<<" "<<query(1,0,2*n-1,0,2*n-1)<<" "<<endl;
       }else{
       	vis[x1]++;
		   vis[x2]++;
	   }
       
       ropos[abs(tren1)]++;
       roneg[abs(tren1)]++;
       if(tren1>0){
           sum++;
       }
      
     
   }
return sum;
   
}

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