Submission #1047520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047520		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	0 / 100	1 ms	4956 KiB

shoes

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include "shoes.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

struct Fen{
    int n;
    vector<int>tree;
    void basla(int N){
        n=N;
        tree.resize(n,0);
        return;
    }
    void update(int tar,int x){
        while(tar<=n){
            tree[tar]+=x;
            tar+=(tar&-tar);
        }
    }
    int query(int tar){
        int res=0;
        while(tar){
            res+=tree[tar];
            tar-=(tar&-tar);
        }
        return res;
    }
};

int n;
int arr[200001];
set<pair<int,int>>st;
vector<int>son[2][100001];
Fen fen;

void ekle(int i){
    if(!son[0][i].size())return;
    st.insert({fen.query(son[0][i].back()-1)+fen.query(son[1][i].back()-1)-(son[0][i].back()<son[1][i].back()?1:0),i});
}

ll count_swaps(vector<int>s) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    n=s.size();
    bool peynir=true;
    for(int i=0;i*2<n;i++){
    	if(i>0||s[i]+s[i+(n/2)]){
    		peynir=false;
    		break;
    	}
    }
	if(peynir)return ((n/2)*((n/2)-1))/2;
    fen.basla(n);
    for(int i=1;i<=n;i++){
        arr[i]=s[i-1];
        fen.update(i,1);
        son[arr[i]<0?0:1][abs(arr[i])].pb(i);
    }
    for(int i=1;(i<<1)<=n;i++){
        reverse(son[0][i].begin(),son[0][i].end());
        reverse(son[1][i].begin(),son[1][i].end());
        ekle(i);
    }
    ll ans=0;
    for(int i=0;i*2<n;i++){
        pair<int,int>p=*st.begin();
        st.erase(st.begin());
        int lef=son[0][p.sc].back();
        int rig=son[1][p.sc].back();
        son[0][p.sc].pop_back();
        son[1][p.sc].pop_back();
        fen.update(lef,-1);
        fen.update(rig,-1);
        ekle(p.sc);
        ans+=p.fr;
    }
    return ans;
}

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