Submission #232101

#	Time	Username	Problem	Language	Result	Execution time	Memory
232101		DanerZein	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	99 ms	16416 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define MAX 200050
using namespace std;
typedef long long ll;
typedef pair<ll,ll>ii;
typedef vector<ii>vi;
ll tree[MAX];//,v[200010];
void add(int x,int v){
  for(int i=x;i<MAX;i+=i&-i){
    tree[i]+=v;
  }
}
int query(int x){
  int s=0;
  for(int i=x;i>0;i-=i&-i){
    s+=tree[i];
  }
  return s;
}
/*void init(int node,int a,int b){
  if(a==b){
    tree[node]=1;
    return;
  }
  init(2*node+1,a,(a+b)/2);
  init(2*node+2,((a+b)/2)+1,b);
  tree[node]=tree[2*node+1]+tree[2*node+2];
}
void update(int node,int a,int b,int pos,int val){
  if(a>pos or b<pos) return;
  if(a==b){tree[node]=val; return;}
  update(2*node+1,a,(a+b)/2,pos,val);
  update(2*node+2,((a+b)/2)+1,b,pos,val);
  tree[node]=tree[2*node+1]+tree[2*node+2];
}
int query(int node,int a,int b, int l,int r){
  // cout<<node<<" "<<a<<" "<<b<<" "<<l<<" "<<r<<endl;
  //return 0;
  if(l>r) return 0;
  if(b<l or a>r) return 0;
  if(l<=a and b<=r) return tree[node];
  return query(2*node+1,a,(a+b)/2,l,r)+query(2*node+2,((a+b)/2)+1,b,l,r);
  }*/
long long count_swaps(std::vector<int> s) {
  vector<vi> sz;
  int n=s.size()/2;
  sz.resize(MAX);
  //cout<<"hi"<<endl;
  for(int i=0;i<s.size();i++){
    sz[abs(s[i])].push_back(ii(s[i],i));
  }
  //  cout<<sz.size()<<endl;
  ll res=0;
  vector<ii>sa;
  for(int i=1;i<=s.size();i++){
    sort(sz[i].begin(),sz[i].end());
    for(int j=0;j<sz[i].size()/2;j++){
      ll l=sz[i][j].second;
      ll r=sz[i][j+sz[i].size()/2].second;
      if(l>r){
	swap(l,r);
	res++;
      }
      sa.push_back(ii(l+1,r+1));
    }
  }
  // cout<<"hi"<<endl;
  sort(sa.begin(),sa.end());
  //  init(0,0,s.size()-1);
  //  cout<<res<<endl;
  for(int i=1;i<=s.size();i++){
    add(i,1);
  }
  for(int i=0;i<sa.size();i++){
    //      cout<<sa[i].second<<" "<<sa[i].first<<endl;
    int x,y;
    // if(sa[i].second-1>=sa[i].first+1){
    // x=query(0,0,s.size()-1,0,sa[i].second-1);
    // y=query(0,0,s.size()-1,0,sa[i].first+1);
    //cout<<x<<" "<<y<<endl;
    x=query(sa[i].second-1);
    y=query(sa[i].first);
    res+=(x-y);
    //   }
    //cout<<res<<endl;
    //   cout<<"hi"<<endl;
    //update(0,0,s.size()-1,sa[i].first,0);
    /*  cout<<query(0,0,s.size()-1,0,s.size())<<endl;
              for(int i=0;i<40;i++){
    cout<<tree[i]<<" ";
    }
    cout<<endl;*/
    //update(0,0,s.size()-1,sa[i].second,0);
    /*    for(int i=0;i<40;i++){
    cout<<tree[i]<<" ";
  }
  cout<<endl;*/
    add(sa[i].first,-1);
    add(sa[i].second,-1);
  }
  return res;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<s.size();i++){
               ~^~~~~~~~~
shoes.cpp:56:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<=s.size();i++){
               ~^~~~~~~~~~
shoes.cpp:58:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<sz[i].size()/2;j++){
                 ~^~~~~~~~~~~~~~~
shoes.cpp:72:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<=s.size();i++){
               ~^~~~~~~~~~
shoes.cpp:75:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<sa.size();i++){
               ~^~~~~~~~~~
shoes.cpp:47:7: warning: unused variable 'n' [-Wunused-variable]
   int n=s.size()/2;
       ^

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