Submission #199102

#	Time	Username	Problem	Language	Result	Execution time	Memory
199102		reda	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	7 ms	2684 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 = 1e5 + 4 ;
ll BIT[MAXN];
bool vis[MAXN];
vector<ll> adj[MAXN];
ll n ;
void update(ll  id,ll  x)
{
        while(id < MAXN)
        {
            BIT[id]+=x;
            id|=id+1;
        }
}
 ll getsum(ll r){
        ll res = 0;
        while(r>=0){
            res+=BIT[r];
            r&=r+1;
            r--;
        }
        return res;
    }
ll  getran(ll  a  ,  ll  b)
{
  if(a)
  return getsum(b)-getsum(a-1);
  return  getsum(b);
}
ll get_id(ll x){
    if(x > 0)return x;
    else return -x+n;
}
long  long count_swaps (vector<int>s)
{
  n  = s.size()/2;
  set<pair<ll,ll>>pq ;
  ll  ans  = 0 ;
  for(ll i =0 ;i <s.size();i++)
  {
    pq.insert({i,s[i]});
    if(s[i]>0)adj[s[i]].pb(i);
    else 
    {
      adj[get_id(s[i])].pb(i);
    }
  }
  for(ll  i= 1 ; i <= 2*n;i++)
  {
    reverse(all(adj[i]));
  }
  while(pq.size())
  {
    if(vis[pq.begin()->first])
    {
      pq.erase(pq.begin());
      continue;
    }
    ll cur  = -pq.begin()->second;
    ll idx = get_id(cur);
    ll to = adj[idx].back();
    adj[get_id(-cur)].pop_back();
    ll  dist=(to+getran(to,MAXN-1))-(pq.begin()->first+getran(pq.begin()->first,MAXN-1));
    if(pq.begin()->second < 0)dist--;
    ans +=dist;
    vis[pq.begin()->first]=1;
    vis[to]=1;
    update(to,1);
  }
  return ans ;
}
/*
int main ()
{
   ios_base::sync_with_stdio(0);
    int n; cin >> n;
    vector<int> v;
    for(int i(0); i < n;i++){
        int x; cin >> x;
        v.push_back(x);
    }
    cout << count_swaps(v);
    return 0;
}*/

Compilation message (stderr)

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

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