Submission #989801

#	Time	Username	Problem	Language	Result	Execution time	Memory
989801		mateuszwes	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	50 ms	21840 KiB

shoes

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

#include "shoes.h"

constexpr int base = 1<<19;
constexpr int debug = 0;
constexpr ll mini = -1e18-7;
constexpr int N = 3e5+7;
constexpr int M = 1e5+7;

vector<int> shoe_index[N];
int ind[N];
bool istaken[N];
ll tree[2*base+7];              //delta do indeksu

void add(int a, int b, ll val){
    a += base-1;
    b += base+1;
    
    while(a/2 != b/2){
        if(!(a&1)){
            tree[a+1] += val;
        }
        a /= 2;
        if(b&1){
            tree[b-1] += val;
        }
        b /= 2;
    }
}

ll query(int v){
    ll ans = 0;
    v += base;
    while(v > 0){
        ans += tree[v];
        v /= 2;
    }
    
    return ans;
}

ll count_swaps(vector<int> s){
    ll ans = 0;
    
    for(int i = 0; i < s.size(); i++){
        shoe_index[s[i]+M].pb(i);
    }
    
    for(int i = 0; i < s.size(); i++){
        if(istaken[i]) continue;
        istaken[i] = 1;
        int index = shoe_index[-s[i]+M][ind[-s[i]+M]];
        istaken[index] = 1;
        
        if(s[i] < 0) ans--;
        
        ans += (index+query(index)-(i+query(i)));
        if(debug) cout << i << ' ' << index << ' ' << ans << ' ' << query(i) << ' ' << query(index) << endl;
        
        add(index, s.size(), -1);
        
        ind[s[i]+M]++;
        ind[-s[i]+M]++;
        
    }
    return ans;
}

Compilation message (stderr)

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