제출 #485824

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
485824		qwerasdfzxcl	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1091 ms	13524 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<int> pos[100100];
pair<int, int> a[100100];

inline int myabs(int x){
    if (x<0) return -x;
    return x;
}

long long count_swaps(std::vector<int> s) {
  	int n = s.size()/2;
    for (int i=n*2-1;i>=0;i--) if (s[i]<0) pos[-s[i]].push_back(i);
    ll ret = 0;
    vector<int> vec(s.size(), -1);
    int cnt = 1;
    for (int i=0;i<n*2;i++) if (s[i]>0){
        vec[i] = cnt*2;
        vec[pos[s[i]].back()] = cnt*2-1;
        if (i<pos[s[i]].back()) ret++;
        else ret--;
        ret += myabs(i-pos[s[i]].back());
        a[cnt] = {i, pos[s[i]].back()};
        if (a[cnt].first>a[cnt].second) swap(a[cnt].first, a[cnt].second);

        pos[s[i]].pop_back();
        cnt++;
    }
    //printf("%lld\n", ret);
    //for (int i=0;i<n*2;i++) printf("%d ", vec[i]);
    //printf("\n");

    for (int i=1;i<=n;i++){
        set<int> st;
        for (int j=a[i].first+1;j<a[i].second;j++){
            if (st.find((vec[j]+1)/2)!=st.end()) ret += 2;
            else st.insert((vec[j]+1)/2);
        }
        //for (auto &x:st) printf("%d ", x);
        //printf("\n");
    }
    return ret/2;
}

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