Submission #1292215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292215		eri16	Arranging Shoes (IOI19_shoes)	C++20	Compilation error	0 ms	0 KiB

shoes

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

using ll = long long;

class ST{
  
private:
    vector <ll> tree;
 
    ll n;
 
    void build(vector <ll>& arr, ll node, ll start, ll end){
        
        if (start==end){tree[node]=arr[start];}
        else{
            ll mid=(start+end)/2;
            build(arr,2*node,start,mid);    
            build(arr,2*node+1,mid+1,end);
            tree[node]=tree[2*node]+tree[2*node+1];
        }
    }
    
    ll query(ll node, ll start, ll end, ll l, ll r){
        if (r<start || l>end){return 0;}
        else if(r>=end && l<=start){return tree[node];}
        else{
            ll mid=(start+end)/2;
            ll lseg=query(2*node,start,mid,l,r);
            ll rseg=query(2*node+1,mid+1,end,l,r);            
            return(lseg+rseg);
        }
    }
    
    void update(ll node, ll start, ll end, ll idx, ll val){
        
        ll mid=(start+end)/2;
        
        if (start==end){
            tree[node]=val;
        }
        
        else if(idx<=mid){
            update(2*node,start,mid,idx,val);
            
            tree[node]=tree[2*node]+tree[2*node+1];
            
        }
        
        else{
            update(2*node+1,mid+1,end,idx,val);
            
            tree[node]=tree[2*node]+tree[2*node+1];            
        }
        
    }
    
    
    
public:
 
    ST(vector<ll>& arr){
        n=arr.size();
        tree.resize(4*n);
        build(arr,1,0,n-1);
    }
    
    ll qu(ll l, ll r){
        return query(1,0,n-1,l,r);
    }
    
    void up(ll idx, ll val){
        update(1,0,n-1,idx,val);    
    }
};

long long count_swaps(vector <int> v){
    ll cnt=0,cur=0,n=v.size();    
    
    vector <ll> alive(n);
    
    for (int i=0; i<n; i++){alive[i]=1;}
    ST st(alive);
    
    map<ll,priority_queue<ll>> mp;
    
    for (ll i=0; i<n; i++){
        mp[v[i]].push(-i);
    }
    
    for (ll i=0; i<n; i++){
        if (i%2==0){
            cur=(v[i])*(-1);
        }    
        else{
            ll idx=mp[cur].top()*(-1);
            cout<<idx<<' ';
            mp[cur].pop();
            mp[-cur].pop();
            alive[idx]=0;
            st.up(idx,0);
            
            cnt+=st.qu(i,idx);
            if (v[i-1]>0){cnt++;}
        }
        cout<<cnt<<'\n';
    }
    return cnt;
}

int main() {
    vector<int> shoes = {2, 1, -1, -2};

    long long swaps = count_swaps(shoes);

    cout << "Number of swaps: " << swaps << "\n";


    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccoZiOwW.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cchAcpoa.o:shoes.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status