Submission #1047789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047789		PieArmy	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	26 ms	12752 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;}
#define int ll
struct Fen{
    int n;
    vector<int>tree;
    void basla(int N){
        n=N;
        tree.resize(n+1,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;
    }
};

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

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

int bf(vector<int>cur){
	if(ll(cur.size())==n){
		for(int i=0;i<n;i+=2){
			if(S[cur[i]]>0||(S[cur[i+1]]+S[cur[i]])!=0)
				return sonsuz;
		}
		vector<int>inv(n);
		for(int i=0;i<n;i++){
			inv[cur[i]]=i;
		}
		swap(cur,inv);
		Fen yem;yem.basla(n);
		for(int i=1;i<=n;i++){
			yem.update(i,1);
		}
		int res=0;
		for(int i=0;i<n;i++){
			res+=yem.query(cur[i]);
			yem.update(cur[i]+1,-1);
		}
		return res;
	}
	set<int>yok;
	for(int i=0;i<n;i++){
		yok.insert(i);
	}
	for(int x:cur){
		yok.erase(x);
	}
	int res=sonsuz;
	for(int x:yok){
		cur.pb(x);
		res=min(res,bf(cur));
		cur.pop_back();
	}
	return res;
}

ll count_swaps(vector<int32_t>s) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    n=s.size();
    S=s;
	if(n<=8){
		return bf({});
	}
    bool peynir=true;
    for(int i=0;i*2<n;i++){
    	if(s[i]>0||(s[i]+s[i+(n/2)])!=0){
    		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++){
    	ll mx=st.begin()->fr,pos=st.begin()->sc;
    	for(pair<int,int>x:st){
    		ll cur=cal(x.sc);
    		if(cur>mx){
    			mx=cur;
    			pos=x.sc;
    		}
    	}
        pair<int,int>p={mx,pos};
        st.erase({0,pos});
        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: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15