Submission #617158

#	Time	Username	Problem	Language	Result	Execution time	Memory
617158		wiwiho	Comparing Plants (IOI20_plants)	C++14	11 / 100	4159 ms	2097152 KiB

plants

#include "plants.h"

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define ef emplace_front
#define pob pop_back()
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

const ll MAX = 1e6;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

void waassert(bool t){
    if(t) return;
    exit(0);
}

int n, K;
vector<int> rec;
vector<bool> use;
vector<vector<int>> ans;

struct Node{
    int mn = 0, pos = 0, tag = 0;
};

Node operator+(Node a, Node b){
    Node c;
    c.mn = min(a.mn, b.mn);
    if(a.mn == c.mn) c.pos = a.pos;
    else c.pos = b.pos;
    return c;
}

vector<Node> st;
#define lc 2 * id + 1
#define rc 2 * id + 2

void build(int L = 0, int R = n - 1, int id = 0){
    if(L == R){
        st[id].mn = rec[L];
        st[id].pos = L;
        return;
    }
    int M = (L + R) / 2;
    build(L, M, lc);
    build(M + 1, R, rc);
    st[id] = st[lc] + st[rc];
}

void addtag(int v, int id){
    st[id].tag += v;
    st[id].mn += v;
}

void push(int id){
    addtag(st[id].tag, lc);
    addtag(st[id].tag, rc);
    st[id].tag = 0;
}

void _modify(int l, int r, int v, int L = 0, int R = n - 1, int id = 0){
    if(l <= L && R <= r){
        addtag(v, id);
        return;
    }
    push(id);
    int M = (L + R) / 2;
    if(r <= M) _modify(l, r, v, L, M, lc);
    else if(l > M) _modify(l, r, v, M + 1, R, rc);
    else{
        _modify(l, r, v, L, M, lc);
        _modify(l, r, v, M + 1, R, rc);
    }
    st[id] = st[lc] + st[rc];
}

void modify(int l, int r, int v){
    l = (l % n + n) % n;
    r = (r % n + n) % n;
    if(l <= r) _modify(l, r, v);
    else{
        _modify(l, n - 1, v);
        _modify(0, r, v);
    }
}

void _print(int L = 0, int R = n - 1, int id = 0){
    if(L == R){
        cerr << st[id].mn << " ";
        return;
    }
    push(id);
    int M = (L + R) / 2;
    _print(L, M, lc);
    _print(M + 1, R, rc);
}

void print(){
    _print();
    cerr << "\n";
}

int getdis(int l, int r){
    l = (l % n + n) % n;
    r = (r % n + n) % n;
    if(l == r) return n;
    if(l > r) r += n;
    return r - l;
}

set<int> zero;
set<pii> sep;

void solve(int rk){
    
    while(st[0].mn == 0){
        int pos = st[0].pos;
        modify(pos, pos, MAX);

        if(zero.empty()){
            zero.insert(pos);
            sep.insert(mp(n, pos));
            continue;
        }
        
        auto it = zero.lower_bound(pos);
        if(it == zero.end()) it = zero.begin();
        int nxt = *it;
        int lst = it == zero.begin() ? *zero.rbegin() : *prev(it);
        sep.erase(mp(getdis(lst, nxt), nxt));
        sep.insert(mp(getdis(lst, pos), pos));
        sep.insert(mp(getdis(pos, nxt), nxt));
        zero.insert(pos);
    }

    int pos = sep.rbegin()->S;
    if(zero.size() == 1){
        sep.clear();
        zero.clear();
    }
    else{
        auto it = zero.lower_bound(pos);
        int nxt = next(it) == zero.end() ? *zero.begin() : *next(it);
        int lst = it == zero.begin() ? *zero.rbegin() : *prev(it);
        sep.erase(mp(getdis(lst, pos), pos));
        sep.erase(mp(getdis(pos, nxt), nxt));
        sep.insert(mp(getdis(lst, nxt), nxt));
        zero.erase(pos);
    }

    use[pos] = true;
    modify(pos - K + 1, pos - 1, -1);

    //cerr << "rk " << rk << " " << pos << "\n";
    for(int i = pos + 1; i < pos + K; i++){
        if(use[i % n]){
            continue;
        }
        ans[pos][i % n] = 1;
    }
    for(int i = pos - 1; i > pos - K; i--){
        if(use[(i + n) % n]) continue;
        ans[pos][(i + n) % n] = 1;
    }
}

vector<bool> vst;
void dfs(int now, int s, int t){
    //cerr << "dfs " << s << " : " << now << "\n";
    ans[s][now] = t;
    vst[now] = true;
    for(int i = 0; i < n; i++){
        if(vst[i]) continue;
        if(ans[now][i] != t) continue;
        dfs(i, s, t);
    }
}

void init(int k, vector<int> _r){
    K = k;
    rec = _r;
    n = rec.size();
    ans.resize(n, vector<int>(n));
    st.resize(4 * n);
    use.resize(n);
    build();

    for(int i = n; i >= 1; i--){
        solve(i);
    }

    for(int i = 0; i < n; i++){
        vst.clear();
        vst.resize(n);
        dfs(i, i, 1);
        dfs(i, i, -1);
    }

}

int compare_plants(int x, int y){
    if(ans[x][y] == 1) return 1;
    else if(ans[y][x] == 1) return -1;

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 11 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25