제출 #667034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
667034		irmuun	Arranging Shoes (IOI19_shoes)	C++17	25 / 100	136 ms	24508 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define ll long long
#define pb push_back
struct segtree{
    int n;
    vector<int>d;
    vector<int>u;
    segtree(vector<int>v){
        n=v.size();
        u=v;
        d.resize(4*n);
        build(1,0,n-1);
    }
    void build(int node,int l,int r){
        if(l==r){
            d[node]=u[l];
            return;
        }
        int mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        d[node]=d[node*2]+d[node*2+1];
    }
    int query(int node,int l,int r,int L,int R){
        if(L > r || R < l || L > R){
            return 0;
        }
        if(L <= l && r <= R){
            return d[node];
        }
        int mid=(l+r)/2;
        return query(node*2,l,mid,L,R)+query(node*2+1,mid+1,r,L,R);
    }   
    void update(int node,int l,int r,int k,int val){
        if(l>k || r<k)return;
        if(l==r){
            d[node]=val;
            return;
        }
        int mid=(l+r)/2;
        update(node*2,l,mid,k,val);
        update(node*2+1,mid+1,r,k,val);
        d[node]=d[node*2]+d[node*2+1];
    }
};


long long diff(vector<int>v,vector<int>u){
    long long res=0;
    int n=v.size();
    for(int i=0;i<n;i++){
        int x;
        for(int j=i;j<n;j++){
            if(v[i]==u[j]){
                x=j;
                break;
            }
        }
        for(int j=i;j<x;j++){
            swap(u[j],u[j+1]);
            res++;
        }
    }
    return res;
}


long long count_swaps(vector<int>s){
    int n=s.size()/2;//number of pair
    if(n<=8){
        vector<int>vec;
        long long ans=100000000;
        for(int i=0;i<s.size();i++){
            if(s[i]>0){
                vec.pb(s[i]);
            }
        }
        vector<int>v;
        sort(vec.begin(),vec.end());
        do{
            v.clear();
            for(int i=0;i<n;i++){
                v.pb(-vec[i]);
                v.pb(vec[i]);
            }
            ans=min(ans,diff(v,s));
        }while(next_permutation(vec.begin(),vec.end()));
        return ans;
    }
    vector<int>pos[n+5];
    vector<int>neg[n+5];
    for(int i=0;i<2*n;i++){
        if(s[i]<0){
            neg[-s[i]].pb(i);
        }
        else{
            pos[s[i]].pb(i);
        }
    }
    int cur=0;
    long long ans=0;
    vector<int>a(2*n);
    for(int i=1;i<=n;i++){
        for(int j=0;j<pos[i].size();j++){
            cur++;
            if(pos[i][j]<neg[i][j]){
                ans++;
            }
            a[neg[i][j]]=cur;
            a[pos[i][j]]=cur;
        }
    }
    vector<int>fi,se;
    fi.resize(2*n);
    se.resize(2*n);
    int l[n+5],r[n+5];
    fill(l+1,l+n+1,-1);
    for(int i=0;i<2*n;i++){
        if(l[a[i]]==-1){
            l[a[i]]=i;
            fi[i]=1;
            se[i]=0;
        }
        else{
            r[a[i]]=i;
            fi[i]=0;
            se[i]=1;
        }
    }
    segtree sg1(fi);
    segtree sg2(se);
    for(int i=0;i<2*n;i++){
        if(l[a[i]]==-1){
            continue;
        }
        ans+=sg1.query(1,0,2*n-1,l[a[i]],r[a[i]]);
        ans-=sg2.query(1,0,2*n-1,l[a[i]],r[a[i]]);
        sg1.update(1,0,2*n-1,l[a[i]],0);
        sg2.update(1,0,2*n-1,r[a[i]],0);
        l[a[i]]=-1;
    }
    return ans;
}

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

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int i=0;i<s.size();i++){
      |                     ~^~~~~~~~~
shoes.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int j=0;j<pos[i].size();j++){
      |                     ~^~~~~~~~~~~~~~
shoes.cpp: In function 'long long int diff(std::vector<int>, std::vector<int>)':
shoes.cpp:54:13: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |         int x;
      |             ^

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