Submission #624904

#	Time	Username	Problem	Language	Result	Execution time	Memory
624904		John3_141592	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	18 ms	4020 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
#define par pair<int,int>
#define f first
#define s second
#define ld long duble
#define ull unsigned long long
#define st short int

using namespace std;

int abi[1000006],N;

void add(int k){
    while(k<=N) abi[k]++,k+=k&-k;
}

ll query(int k){
    ll s=0;
    while(k) s+=abi[k],k-=k&-k;
    return s;
}

long long count_swaps(std::vector<int> vec) {
    stack <int> pila1,pila2,pilam1,pilam2;
    for(int i=vec.size()-1;i>=0;i--){
        if(vec[i]==1) pila1.push(i);
        if(vec[i]==-1) pilam1.push(i);
        if(vec[i]==2) pila2.push(i);
        if(vec[i]==-2) pilam2.push(i);
    }
    int n=vec.size();
    N=n;
    ll solve=0;
    fill(abi,abi+n,0);
    bool vis[n];
    fill(vis,vis+n,false);
    for(int i=0;i<n;i++){
        if(vis[i]) continue;
        if(vec[i]==1){
            if(pilam1.empty()) continue;
            while(pilam1.top()<i){
                pilam1.pop();
                if(pilam1.empty()) break;
            }
            if(pilam1.empty()) continue;
            solve+=pilam1.top()-i-query(pilam1.top())+query(i);
            add(pilam1.top());
            vis[pilam1.top()]=true;
            pilam1.pop();
        }
        if(vec[i]==-1){
            if(pila1.empty()) continue;
            while(pila1.top()<i){
                pila1.pop();
                if(pila1.empty()) break;
            }
            if(pila1.empty()) continue;
            solve+=pila1.top()-i-1-query(pila1.top())+query(i);
            add(pila1.top());
            vis[pila1.top()]=true;
            pila1.pop();
        }
        if(vec[i]==2){
            if(pilam2.empty()) continue;
            while(pilam2.top()<i){
                pilam2.pop();
                if(pilam2.empty()) break;
            }
            if(pilam2.empty()) continue;
            solve+=pilam2.top()-i-query(pilam2.top())+query(i);
            add(pilam2.top());
            vis[pilam2.top()]=true;
            pilam2.pop();
        }
        if(vec[i]==-2){
            if(pila2.empty()) continue;
            while(pila2.top()<i){
                pila2.pop();
                if(pila2.empty()) break;
            }
            if(pila2.empty()) continue;
            solve+=pila2.top()-i-1-query(pila2.top())+query(i);
            add(pila2.top());
            vis[pila2.top()]=true;
            pila2.pop();
        }
    }
    return solve;
}

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