Submission #232080

#	Time	Username	Problem	Language	Result	Execution time	Memory
232080		DanerZein	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	6 ms	2720 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define MAX 100010
using namespace std;
typedef long long ll;
typedef pair<ll,ll>ii;
typedef vector<ii>vi;
ll tree[800010],v[200010];

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 and b==pos){tree[node]=val; return;}
  update(2*node+1,a,(a+b)/2,pos,val);
  update(2*node+2,b,(a+b)/2+1,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(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);
  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,r));
    }
  }
  // cout<<"hi"<<endl;
  init(0,0,s.size()-1);
  //cout<<"hi"<<endl;
  /* for(int i=0;i<10;i++){
    cout<<tree[i]<<" ";
  }
  cout<<endl;
  cout<<res<<endl;*/
  for(int i=0;i<sa.size();i++){
    //  cout<<sa[i].second<<" "<<sa[i].first<<endl;
    int x,y;
    x=query(0,0,s.size()-1,0,sa[i].second);
    y=query(0,0,s.size()-1,0,sa[i].first);
    //cout<<x<<" "<<y<<endl;
    res+=(x-y);
    //   cout<<"hi"<<endl;
    update(0,0,s.size()-1,sa[i].first,-1);
    update(0,0,s.size()-1,sa[i].second,-1);
  }
  return res;
}

Compilation message (stderr)

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

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