Submission #811023

#	Time	Username	Problem	Language	Result	Execution time	Memory
811023		Essa2006	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	333 ms	153996 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
#include <cstdio>
#include <cassert>
using namespace std;
#define ll long long 
#define endl '\n'
#define FF firtst
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int pr=20, s_p=(1<<pr), e_p=(1<<(pr+1))-1;
vector<int>SS;
map<int, queue<int>>mp;
void pre(){
    SS.clear(), mp.clear();
    SS.resize(1<<(pr+1));
}
void update(int id, int u, int v, int l, int r){
    if(l>v || r<u)
        return;
    if(l>=u && r<=v){
        SS[id]++;
        return;
    }
    int md=(l+r)/2;
    update(id*2, u, v, l, md);
    update(id*2+1, u, v, md+1, r);
        
}
int get(int ind){
    ll res=SS[ind];
    while(ind/=2)
        res+=SS[ind];
    return res;
}
ll count_swaps(vector<int> A){
    int n=A.size();
    pre();
    ll ans=0;
    for(int i=0;i<n;i++){
        if(A[i]>0 && !mp[-A[i]].empty()){
            int u=mp[-A[i]].front();
            mp[-A[i]].pop();
            u+=get(u+s_p);
            ans+=i-u-1;
            if(u!=i-1)
                update(1, u+1+s_p, i-1+s_p, s_p, e_p);
        }
        else if(A[i]<0 && !mp[-A[i]].empty()){
            int u=mp[-A[i]].front();
            mp[-A[i]].pop();
            u+=get(u+s_p);
            ans+=i-u;
            update(1, u+s_p, i-1+s_p, s_p, e_p);
        }
        else{
            mp[A[i]].push(i);
        }
    }
    return ans;
    
}
//ll count_swaps2(vector<int> A){
//    bool same=1;
//    int n=A.size();
//    for(int i=1;i<n;i++){
//        if(abs(A[i])!=abs(A[i-1]))
//            same=0;
//    }
//    if(n/2<=1000){
//        int ans=0;
//        for(int i=0;i<n;i++){
//            if(A[i]>0){
//                bool found=0;
//                int ind=0;
//                for(int j=0;j<i;j++){
//                    if(-A[j]==A[i] && A[j+1]!=-A[j]){
//                        found=1;
//                        ind=j;
//                        break;
//                    }
//                }
//                if(found){
//                    for(int j=i-1;j>ind;j--){
//                        swap(A[j], A[j+1]);
//                        ans++;
//                    }
//                }
//            }
//            else if(A[i]<0){
//                bool found=0;
//                int ind=0;
//                for(int j=0;j<i;j++){
//                    if(-A[j]==A[i] && (!j || A[j]!=-A[j-1])){
//                        found=1;
//                        ind=j;
//                        break;
//                    }
//                }
//                if(found){
//                    for(int j=i-1;j>=ind;j--){
//                        swap(A[j], A[j+1]);
//                        ans++;
//                    }
//                }
//            }
//        }
//        return ans;
//    }
//    if(n/2>1000 && !same){
//        ll ans=A.size()/2;
//        return ans*(ans-1)/2;
//    }
//    
//} 
// 
//int main() {
//	int n;
//	assert(1 == scanf("%d", &n));
//	vector<int> S(2 * n);
//	for (int i = 0; i < 2 * n; i++)
//		assert(1 == scanf("%d", &S[i]));
//	fclose(stdin);
//
//	long long result = count_swaps(S);
//
//	printf("%lld\n", result);
//	fclose(stdout);
//	return 0;
//}

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