제출 #316950

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
316950		Jarif_Rahman	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	213 ms	32428 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int n, k;
vector<int>v;
vector<ll> seg;
void upd(int in, ll x){
    in+=k/2;
    seg[in] = x, in/=2;
    while(in > 0){
        seg[in] = seg[2*in] + seg[2*in+1];
        in/=2;
    }
}
ll sum(int l, int r){
    l+=k/2, r+=k/2;
    ll s = 0;
    while(l <= r){
        if(l%2 == 1) s+=seg[l], l++;
        if(r%2 == 0) s+=seg[r], r--;
        l/=2, r/=2;
    }
    return s;
}
long long count_swaps(vector<int> S){
    v = S;
    n = v.size()/2;
    k = 1; while(k <= 2*n) k*=2; k*=2;
    seg.resize(k, 0);
    vector<int> a(2*n);
    vector<pair<int, int>> sth(n+1, {0,0});
    for(int i = 0; i < 2*n; i++){
        if(v[i] > 0) sth[v[i]].sc++;
        else sth[-v[i]].f++;
    }
    int z = 0;
    for(int i = 0; i < 2*n; i++){
        int x = abs(v[i]);
        if(v[i] > 0){
            if(sth[x].sc <=  sth[x].f){
                a[2*z] = -x;
                a[2*z+1] = x;
                z++;
            }
            sth[x].sc--;
        }
        else{
            if(sth[x].f <=  sth[x].sc){
                a[2*z] = -x;
                a[2*z+1] = x;
                z++;
            }
            sth[x].f--;
        }
    }
    vector<vector<int>> va(2*n+1), vb(2*n+1);
    vector<int> p(2*n);
    for(int i = 0; i < 2*n; i++) va[a[i]+n].pb(i);
    for(int i = 0; i < 2*n; i++) vb[v[i]+n].pb(i);
    for(int i = 0; i <= 2*n; i++){
        if(va[i].empty()) continue;
        for(int j = 0; j < va[i].size(); j++) p[vb[i][j]] = va[i][j];
    }
    ll ans = 0;
    for(int i = 0; i < 2*n; i++){
        if(p[i]!=2*n-1) ans+=sum(p[i]+1, 2*n-1);
        upd(p[i], 1);
    }
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:67:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int j = 0; j < va[i].size(); j++) p[vb[i][j]] = va[i][j];
      |                        ~~^~~~~~~~~~~~~~

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