| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 143861 | shdut | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "shoes.h"
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
using namespace std;
#define inf 1000000007
#define SZ(x) x.size()
#define N 100005
#define pb push_back
#define x first
#define y second
#define ls p<<1
#define rs p<<1|1
#define vi std::vector<int>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define DBG(x) cerr << (#x) << "=" << x << "\n";
std::map<vi, int>f;
int check(vi &s){
rep(i, 0, SZ(s)-1){
if(s[i] + s[i+1])return 0;
i++;
}
return 1;
}
int go(vi &s, int h = 0){
if(f.count(s))return f[s];
//for(auto &x : s)printf("%d ", x);
//puts("");
if(check(s))return f[s] = 0;
if(h == 25)return inf;
int ret = inf;
rep(i, 0, SZ(s))if(s[i] < 0){
rep(j, 0, SZ(s)){
if(s[j] + s[i] == 0 && j != i + 1){
vi t;
//cerr << s[i] << " " << s[j] << " ..\n";
if(j < i){
rep(k, 0, j)t.pb(s[k]);
rep(k, j+1, i+1)t.pb(s[k]);
t.pb(s[j]);
rep(k, i+1, SZ(s))t.pb(s[k]);
ret = std::min(ret, go(t, h+1) + i-j);
}
else{
rep(k, 0, i+1)t.pb(s[k]);
t.pb(s[j]);
rep(k, i+1, j)t.pb(s[k]);
rep(k, j+1, SZ(s))t.pb(s[k]);
ret = std::min(ret, go(t, h+1) + j - i - 1);
}
}
}
}
return f[s] = ret;
}
int t[N << 2];
void build(int p, int l, int r){
if(l == r){
t[p] = 1;
return;
}
int m = (l + r) >> 1;
build(ls, l, m);
build(rs, m+1, r);
t[p] = t[ls] + t[rs];
}
void upd(int p, int l, int r, int x, int v){
t[p] += v;
if(l == r){
return;
}
int m = (l+r) >> 1;
if(x <= m)upd(ls, l, m, x, v);
else upd(rs, m+1, r, x, v);
}
int query(int p, int l, int r, int x, int y){
if(x > y)return 0;
if(l >= x && r <= y)return t[p];
int m = (l+r) >> 1, ans = 0;
if(x <= m)ans = query(ls, l, m, x, y);
if(y > m)ans += query(rs, m+1, r, x, y);
return ans;
}
std::set<pair<int, int>>a, b;
long long count_swaps(std::vector<int> s) {
int n = s.size();
build(1, 0, n-1);
a.clear();
b.clear();
rep(i, 0, n){
if(s[i] < 0)a.insert({-s[i], i});
else b.insert({s[i], i});
}
vi vis(n, 0);
long long ans = 0;
int l = 0, r = n - 1, x, v;
while(l <= r){
if(vis[l]){
l++;continue;
}
if(vis[r]){
r--;
continue;
}
if(s[r] < 0){
x = -s[r];
auto it = b.lower_bound({x, n});
assert(it != b.begin());
it--;
vis[it->y] = 1;
v = query(1, 0, n-1, it->y+1, r-1);
ans += v + 1;
upd(1, 0, n-1, it->y, -1);
b.erase(it);
a.erase({x, r});
r--;
}
else if(s[l] < 0){
x = -s[l];
auto it = b.lower_bound({x, 0});
assert(it != b.end());
vis[it->y] = 1;
v = query(1, 0, n-1, l+1, it->y-1);
ans += v;
upd(1, 0, n-1, it->y, -1);
b.erase(it);
a.erase({x, l});
l++;
}
else{
x = s[r];
auto it = a.lower_bound({x, n});
assert(it != b.begin());
it--;
vis[it->y] = 1;
v = query(1, 0, n-1, it->y+1, r-1);
ans += v;
upd(1, 0, n-1, it->y, -1);
b.erase(it);
a.erase({x, r});
r--;
}
}
//int res = go(s);
//DBG(res)
return ans;
}