제출 #1045406

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1045406		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	273 ms	83188 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) {
    int n=s.size()>>1,CC=0;
    vector<int>sup,sup2;
    sup.resize(2*n);
    sup2.resize(2*n);
    for(int i=0;i<n*2;i++)
        if(s[i]<0) sup[i]=2*CC,
            otherpos[-s[i]].push(2*CC+++1);
    for(int i=0;i<n*2;i++)if(s[i]>0)
        sup[i]=otherpos[s[i]].front(),otherpos[s[i]].pop();
    CC=0;
    for(int i=0;i<n*2;i++)
        if(s[i]>0) sup2[i]=2*CC+1,
            otherpos[s[i]].push(2*CC++);
    for(int i=0;i<n*2;i++)if(s[i]<0)
        sup2[i]=otherpos[-s[i]].front(),otherpos[-s[i]].pop();
    return min(calc(sup),calc(sup2));
}

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