Submission #199103

#	Time	Username	Problem	Language	Result	Execution time	Memory
199103		reda	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	205 ms	33528 KiB

shoes

#include<bits/stdc++.h>
#define ll  long long 
#pragma GCC optimize ("Ofast","unroll-loops")
using namespace std;
#define  all(x) x.begin(),x.end()
#define pb push_back
const ll MAXN = 6e5 + 4 ;
vector<int> pos[MAXN];
bool used[MAXN];
ll bit[MAXN];
ll n;
void upd(int id,int x)
{
      while(id < MAXN){
            bit[id]+=x;
            id|=id+1;
        }
    }
int sum(int r)
{
  int res = 0;
  while(r>=0){
  res+=bit[r];
  r&=r+1;
  r--;
  }
  return res;
}
int segm(int l,int r){
        int ans = sum(r);
        if(l)ans-=sum(l-1);
        return ans;
    }

 
int get_id(int x){
    if(x > 0)return x;
    else return -x+n;
}
 
long long count_swaps(vector<int> s) {
    long long ans = 0;
    n = s.size()/2;
    set<pair<int,int> > qwe;
    for(int i(0); i < s.size();i++){
        qwe.insert({i,s[i]});
        if(s[i] > 0)pos[s[i]].push_back(i);
        else{
            int id = get_id(s[i]);
            pos[id].push_back(i);
        }
    }
    for(int i(1); i <= 2*n;i++){
        reverse(pos[i].begin(),pos[i].end());
    }
    while(qwe.size()){
        if(used[qwe.begin()->first]){
            qwe.erase(qwe.begin());
            continue;
        }
        int now = -qwe.begin()->second;
        int id = get_id(now);
        int to_pos = pos[id].back();
        pos[id].pop_back();
        pos[get_id(-now)].pop_back();
        int dist = (to_pos+segm(to_pos,MAXN-1))-(qwe.begin()->first+segm(qwe.begin()->first,MAXN-1));
        if(qwe.begin()->second < 0)dist--;
        ans+=dist;
        used[qwe.begin()->first] = 1;
        used[to_pos] = 1;
        upd(to_pos,1);
    }
    return ans;
}
 

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:45:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < s.size();i++){
                   ~~^~~~~~~~~~

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