Submission #169912

#	Time	Username	Problem	Language	Result	Execution time	Memory
169912		whttt	Arranging Shoes (IOI19_shoes)	C++14	25 / 100	936 ms	15716 KiB

shoes

#include <vector>
#include <iostream>
#include <algorithm>
#define ll long long

using namespace std;

ll count_swaps(vector<int> S){
    ll n = S.size()/2;
    if(n == 1){
        if(S[0] < 0){
            return 0;
        } else {
            return 1;
        }
    }
    vector<vector<ll>> vyskytR;
    vector<vector<ll>> vyskytL;
    for(ll i = 0;i <= n;i++){
        vyskytL.push_back({});
        vyskytR.push_back({});
    }
    ll sol = 0;
    ll sqrtt = 1;
    while(sqrtt * sqrtt < 2*n){
        sqrtt++;
    }
    ll sqrtDec[2*n/sqrtt];
    ll sum[2*n];
    for(ll i = 0;i < 2*n/sqrtt;i++){
        sqrtDec[i] = 0;
    }
    for(ll i = 0;i < 2*n;i++){
        sum[i] = 0;
    }
    for(ll i = 0;i < 2*n;i++){
        if(S[i] < 0){
            vyskytL[-S[i]].push_back(i);
        } else {
            vyskytR[S[i]].push_back(i);
        }
    }
    for(ll i = 0;i < n;i++){
        reverse(vyskytR[i].begin(),vyskytR[i].end());
        reverse(vyskytL[i].begin(),vyskytL[i].end());
    }
    ll where = 0;
    ll where2 = 0;
    ll countt = 0;
    ll start;
    ll shoes = n;
    while(1){
        if(where >= 2*n || shoes == 0){
            break;
        }
        if(sum[where]==1){
            where++;
            continue;
        }
        if(S[where] < 0){
            where2 = vyskytR[-S[where]][vyskytR[-S[where]].size()-1];
            // countt sa nastavi na pocet pouzitych medzi where a where2
            countt = 0;
            start = where;
            while(1){
                if(start > where2){
                    break;
                }
                if(start % sqrtt == 0 && start+sqrtt-1 <= where2){
                    countt += sqrtDec[start/sqrtt];
                    start += sqrtt;
                } else {
                    countt += sum[start];
                    start++;
                }
                //cout << countt << endl;
                //cout << start << endl;
            }
            sol += where2-where-1-countt;
            vyskytR[-S[where]].pop_back();
            sum[where2] = 1;
            sqrtDec[where2/sqrtt]++;
            where++;
            vyskytL[-S[where-1]].pop_back();
            //cout << -S[where-1] << "???" << endl;
        } else {
            where2 = vyskytL[S[where]][vyskytL[S[where]].size()-1];
            // countt sa nastavi na pocet pouzitych medzi where a where2
            countt = 0;
            start = where;
            while(1){
                if(start > where2){
                    break;
                }
                if(start % sqrtt == 0 && start+sqrtt-1 <= where2){
                    countt += sqrtDec[start/sqrtt];
                    start += sqrtt;
                } else {
                    countt += sum[start];
                    start++;
                }
            }
            sol += where2-where-countt;
            vyskytL[S[where]].pop_back();
            sum[where2] = 1;
            sqrtDec[where2/sqrtt]++;
            where++;
            vyskytR[S[where-1]].pop_back();
        }
        shoes--;
        //cout << countt << endl;
        //cout << where-1 << " " << where2 << endl;
        //cout << sol << endl;
        //cout << "----" << endl;
    }
    //cout << sqrtt << endl;
    return sol;
}

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