Submission #390123

#	Time	Username	Problem	Language	Result	Execution time	Memory
390123		ioi	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	525 ms	409020 KiB

shoes

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

using namespace std ;
const int N = 6e5 ;
int add = 2e5 ;

queue<int> pos[N];

int done[N] ;


 struct BIT{

        int sz ;
        vector<long long> v;

        explicit BIT(int n){
            sz = n ;
            v.resize(n);
        }

        long long  get(int i){
            long long ret = 0 ;

            for(i ++ ; i ; i -=(i & -i))
                ret += v[i - 1];
            return ret ;

        }


        void update(int i , long long val){
            for(i ++ ; i <= sz ; i += (i & -i))
                v[i - 1] += val ;

        }

        long long query(int l , int r){
            return get(r) - get(l - 1);

        }
    };
long long count_swaps(vector<int> s) {

    for(int i = 0 ; i < s.size() ; i ++){
        pos[s[i] + add].push(i);

    }

    BIT bit(s.size());

    for(int i = 0 ;i < s.size() ; i ++)
        bit.update(i , 1);
    int ans = 0 ;

    for(int i = 0 ; i < s.size() ; i ++){
        if(done[i])continue ;


        int p = pos[-s[i] + add].front();
        pos[-s[i] + add].pop();

        done[p] ++;
        pos[s[i] + add].pop();
       // cout << i << " " << p << endl ;
        ans += bit.query(i + 1 , p);
        bit.update(p , -1);

        if(s[i] < 0)ans -- ;

    }


	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 0 ; i < s.size() ; i ++){
      |                     ~~^~~~~~~~~~
shoes.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i = 0 ;i < s.size() ; i ++)
      |                    ~~^~~~~~~~~~
shoes.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i = 0 ; i < s.size() ; i ++){
      |                     ~~^~~~~~~~~~

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