제출 #195673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
195673		Swan	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	213 ms	34012 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define stop system("pause")
#define stop2 char o; cin >> o
#define INP freopen("pcb.in","r",stdin)
#define OUTP freopen ("pcb.out","w",stdout)
using namespace std;

const int maxn = 610000;
vector<int> pos[610000];
bitset<maxn> used;

int n;

namespace fen{
    int bit[maxn];
    void upd(int id,int x){
        while(id < maxn){
            bit[id]+=x;
            id|=id+1;
        }
    }
    int sum(int r){
        int res = 0;
        while(r>=0){
            res+=bit[r];
            r&=r+1;
            r--;
        }
        return res;
    }
    int segm(int l,int r){
        int ans = sum(r);
        if(l)ans-=sum(l-1);
        return ans;
    }
}

int get_id(int x){
    if(x > 0)return x;
    else return -x+n;
}

long long count_swaps(std::vector<int> s) {
    long long ans = 0;
    n = s.size()/2;
    set<pair<int,int> > qwe;
    for(int i(0); i < s.size();i++){
        qwe.insert({i,s[i]});
        if(s[i] > 0)pos[s[i]].push_back(i);
        else{
            int id = get_id(s[i]);
            pos[id].push_back(i);
        }
    }
    for(int i(1); i <= 2*n;i++){
        reverse(pos[i].begin(),pos[i].end());
    }
    while(qwe.size()){
        if(used[qwe.begin()->first]){
            qwe.erase(qwe.begin());
            continue;
        }
        int now = -qwe.begin()->second;
        int id = get_id(now);
        int to_pos = pos[id].back();
        pos[id].pop_back();
        pos[get_id(-now)].pop_back();
        int dist = (to_pos+fen::segm(to_pos,maxn-1))-(qwe.begin()->first+fen::segm(qwe.begin()->first,maxn-1));
        //cout << "W " << (to_pos+fen::segm(to_pos,maxn-1)) << ' ' << (qwe.begin()->first+fen::segm(qwe.begin()->first,maxn-1)) << endl;
        if(qwe.begin()->second < 0)dist--;
        ans+=dist;
        used[qwe.begin()->first] = 1;
        used[to_pos] = 1;
        fen::upd(to_pos,1);
        //cout << ans << ' ' << dist << endl;
    }
    return ans;
}

/*
6
-2 2 2 -2 -2 2
*/
/*
main(){
    ios_base::sync_with_stdio(0);
    int n; cin >> n;
    vector<int> v;
    for(int i(0); i < n;i++){
        int x; cin >> x;
        v.push_back(x);
    }
    cout << count_swaps(v);
    return 0;
}*/
/*
4
2 1 -1 -2
6
-2 2 2 -2 -2 2
*/

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

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:48:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < s.size();i++){
                   ~~^~~~~~~~~~

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