Submission #390126

#	Time	Username	Problem	Language	Result	Execution time	Memory
390126		ioi	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	273 ms	208228 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
 
using namespace std ;
const int N = 3e5 ;
int add = 1e5 ;
 
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);
    long long 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: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15