Submission #1323311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1323311		superomego	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	70 ms	20496 KiB

shoes

#include <bits/stdc++.h>
using namespace std;

void fwt(long long s, long long i, vector<long long> &v, vector<long long> &f){
    
    if(i >= v.size()) return;
    
    if(i > 0) for(int di = -s+1; di < 1; ++di) f[i] += v[i+di];
    else f[0] = v[0];
    
    int c = i, inc = 1;
    while(inc < s){
        fwt(inc, c+inc, v, f);
        inc = inc << 1;
    }
    
    return;
    
}

long long getpref(int i, int j, vector<long long> &f){
    
    if(i > 0) return getpref(0, j, f) - getpref(0, i-1, f);
    
    long long res = f[0];
    int k = j, inc = 1;
    
    while(k > 0){
        
        if(k & inc){
            res += f[k];  
            k -= inc;
        }
        
        inc = inc << 1;
    }
    
    return res;
}

void setpref(int i, long long v, vector<long long> &vi, vector<long long> &fwt){

    if(i == 0){
        fwt[0] = v;
        return;
    } 
    
    int dt = v - vi[i], nx = i, lsb = 1;
    vi[i] = v;
    
    while(nx < fwt.size()){
        fwt[nx] += dt;
        while(not (nx & lsb)) lsb = lsb << 1;
        nx += lsb;
    }
    
}

long long count_swaps(vector<int> S){
    
    long long n = S.size(), ret = 0;
    unordered_map<int, pair<long long, long long>> v;
    
    set<tuple<long long, long long, long long>> s;
    vector<long long> pref(2*n, 0);
    vector<long long> ofwt(2*n, 0);
    
    for(int i = 0; i < S.size(); ++i){
        
        if(v.find(abs(S[i])) == v.end()) v[abs(S[i])] = {-1, -1};
        if(S[i] < 0) v[-S[i]].first = i;
        else v[S[i]].second = i;
    }
    
    for(auto &[k, w] : v){
        
        auto it1 = w.first, it2 = w.second;
        if(it1 > it2) s.insert({it1, it2, 0});
        else s.insert({it2, it1, -1});
        
        
    }
    
    for(auto it = s.rbegin(); it != s.rend(); ++it){
        
        long long val = getpref(get<1>(*it), get<0>(*it), ofwt);
        ret += get<0>(*it) + get<2>(*it) - get<1>(*it) - val;
        if(not pref[get<1>(*it)]) setpref(get<1>(*it), 1, pref, ofwt);
        
    }
    
    return ret;
   
}

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