Submission #856453

#	Time	Username	Problem	Language	Result	Execution time	Memory
856453		IS_Rushdi	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	84 ms	17232 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;

struct segment_tree{
    vector<int>a;
    int sz = 1;
    segment_tree(int n){
        while(sz < n) sz*=2;
        a.assign(sz*2,0);
    }
    void update(int i,int v,int x=0,int lx=0,int rx=-1){
        if(rx == -1) rx = sz;
        if(rx-lx == 1){
            a[x] = v;
            return;
        }
        int m = (lx+rx)/2;
        if(i < m){
            update(i,v,x*2+1,lx,m);
        }else{
            update(i,v,x*2+2,m,rx);
        }
        a[x] = a[x*2+1] + a[x*2+2];
    }
    int get(int l,int r,int x=0,int lx=0,int rx=-1){
        if(rx == -1) rx = sz;
        if(rx <= l || lx >= r) return 0;
        if(l <= lx && r >= rx) return a[x];
        int m = (lx+rx)/2;
        int s1 = get(l,r,x*2+1,lx,m);
        int s2 = get(l,r,x*2+2,m,rx);
        return s1+s2;
    }
};
long long count_swaps(vector<int> a){
    int n = a.size();
    int N = n/2;
    vector<vector<int>>idx(n+1);
    vector<int>ptr(n+1,0);
    long long ans = 0;
    vector<bool>vis(n,0);
    for(int i = 0; i < n; i++){
        idx[a[i]+N].push_back(i);
    }
    segment_tree st(n);
    for(int i = 0; i < n; i++){
        if(vis[i]) continue;
        int search = -1;
        if(a[i] > 0){
           int x = a[i]*2;
           int y = a[i]+N;
           search = y-x;
           ans++;
        }else{
            int x = (-a[i])+N;
            search = x;
        }
        int j = idx[search][ptr[search]];
        ptr[search]++;
        ptr[a[i]+N]++;
        // cout << j << ' ';
        vis[j] = 1;
        st.update(j,1);
        j -= st.get(i,j);
        // cout << j << ' ' << i << '\n';
        cout.flush();
        ans += j-(i+1);
        // cout << ans << '\n';cout.flush();
    }
	return ans;
}
// int main(){
//     vector<int> a = {2, 1, -1, -2};
//     cout << count_swaps(a) << '\n';
// }

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