Submission #143867

#	Time	Username	Problem	Language	Result	Execution time	Memory
143867		shdut	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	334 ms	14328 KiB

shoes

#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 200005
#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});
        //    //std::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});
            //std::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);
            a.erase(it);
            b.erase({x, r});
            r--;
        }
    }
    //int res = go(s);
    //DBG(res)
    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'int check(std::vector<int>&)':
shoes.cpp:18:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, a, b) for(int i = a; i < b; i++)
shoes.cpp:24:9:
     rep(i, 0, SZ(s)-1){
         ~~~~~~~~~~~~~                  
shoes.cpp:24:5: note: in expansion of macro 'rep'
     rep(i, 0, SZ(s)-1){
     ^~~
shoes.cpp: In function 'int go(std::vector<int>&, int)':
shoes.cpp:18:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, a, b) for(int i = a; i < b; i++)
                                       ^
shoes.cpp:37:5: note: in expansion of macro 'rep'
     rep(i, 0, SZ(s))if(s[i] < 0){
     ^~~
shoes.cpp:18:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, a, b) for(int i = a; i < b; i++)
                                       ^
shoes.cpp:38:9: note: in expansion of macro 'rep'
         rep(j, 0, SZ(s)){
         ^~~
shoes.cpp:18:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, a, b) for(int i = a; i < b; i++)
                                       ^
shoes.cpp:46:21: note: in expansion of macro 'rep'
                     rep(k, i+1, SZ(s))t.pb(s[k]);
                     ^~~
shoes.cpp:18:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, a, b) for(int i = a; i < b; i++)
                                       ^
shoes.cpp:53:21: note: in expansion of macro 'rep'
                     rep(k, j+1, SZ(s))t.pb(s[k]);
                     ^~~

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