Submission #1244334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244334		superomego	Arranging Shoes (IOI19_shoes)	C++20	25 / 100	111 ms	29884 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<vector<long long>, vector<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])] = {vector<long long>(), vector<long long>()};
        if(S[i] < 0) v[-S[i]].first.push_back(i);
        else v[S[i]].second.push_back(i);
    }
    
    for(auto &[k, w] : v){
        
        auto it1 = w.first.rbegin(), it2 = w.second.rbegin();
        while(it1 != w.first.rend()){
            
            if((*it1) > (*it2)) s.insert({(*it1), (*it2), 0});
            else s.insert({(*it2), (*it1), -1});
            it1++; it2++;
            
        }
        
    }
    
    for(auto it = s.rbegin(); it != s.rend(); ++it){
        
        long long val = getpref(get<1>(*it), 2*n - 1, 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: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15