Submission #1045456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045456		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1028 ms	137096 KiB

shoes

#include "shoes.h"
#include<bits/extc++.h>
#include<bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
queue<int> otherpos[100100];
long long calc(vector<int>v){
    long long ans=0;
    int K=0;
    tree<int,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update>st;
    for(auto i:v) {
        st.insert(i);
        ans+=K++-st.order_of_key(i);
    }
    return ans;
}
long long count_swaps(std::vector<int> s) {
    long long ans=1e9;
    int n=s.size()>>1;
    vector<int>sup;
    sup.resize(2*n);
    vector<int>perm(n),perm2(n),CR(n);
    int CC=0;
    iota(perm.begin(),perm.end(),0);
    for(int i=0;i<n*2;i++) if(s[i]<0)
        otherpos[-s[i]].push(CC++);
    for(int i=0;i<n*2;i++) if(s[i]>0) {
        int x=otherpos[s[i]].front();
        CR[x]=CC;
        otherpos[s[i]].pop();
        perm2[CC++]=x;
    }
    for(int i=0;i<n;i++)for(int j=1;j<n-i;j++)
        if(perm[j]<perm[j-1]&&CR[j]<CR[j-1]^perm2[CR[j]]<perm2[CR[j-1]])
            swap(perm[j],perm[j-1]),swap(perm2[CR[j]],perm2[CR[j-1]]);
    CC=0;
    for(int i=0;i<n*2;i++)
        if(s[i]<0) sup[i]=2*perm[CC],
            otherpos[-s[i]].push(2*perm[CC++]+1);
    for(int i=0;i<n*2;i++)if(s[i]>0)
        sup[i]=otherpos[s[i]].front(),otherpos[s[i]].pop();
    return calc(sup);
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:34:36: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   34 |         if(perm[j]<perm[j-1]&&CR[j]<CR[j-1]^perm2[CR[j]]<perm2[CR[j-1]])
shoes.cpp:18:15: warning: unused variable 'ans' [-Wunused-variable]
   18 |     long long ans=1e9;
      |               ^~~

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