Submission #679807

#	Time	Username	Problem	Language	Result	Execution time	Memory
679807		vicious	Arranging Shoes (IOI19_shoes)	C++17	0 / 100	2 ms	2644 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int N = 100010;
int n,arr[N],from[N],vis[N];
vector<int> p[N];
ll ans;

ll fw[N], fw2[N];
void update(int x, int y, int v) { //inclusive
    for (int tx=x; tx < N; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1);
    for (int ty=y+1; ty < N; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y; 
}
ll sum (int x) {
    int res = 0;
    for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx];
    return res;
}
ll query(int x, int y) { //inclusive
    return sum(y)-sum(x-1);
}

long long count_swaps(std::vector<int> s) {
    n = s.size();
    for (int i = 1; i <= n; ++i) arr[i]=s[i-1];
    for (int i = n; i >= 1; --i) {
        update(i,i,i);
        p[arr[i]].push_back(i);
        if (!p[-arr[i]].size()) continue;
        from[i] = p[-arr[i]].back();
    }
    for (int i = 1; i <= n; ++i) {
        if (!from[i] || vis[i]) continue;
        int rx = query(from[i],from[i]);
        int lx = query(i,i);
        int actual = abs(arr[i])*(lx%2?-1:1);
        ans += rx-lx+(actual!=arr[i])-1;
        update(1,rx,1);
        vis[from[i]]=1;
    }
    return ans;
}

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