Submission #522086

#	Time	Username	Problem	Language	Result	Execution time	Memory
522086		tabr	Handcrafted Gift (IOI20_gift)	C++17	45 / 100	1561 ms	24592 KiB

gift

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

#ifdef tabr
void craft(string s);
#else
#include "gift.h"
#endif

struct dsu {
    vector<int> p;
    vector<int> sz;
    int n;

    dsu(int _n) : n(_n) {
        p = vector<int>(n);
        iota(p.begin(), p.end(), 0);
        sz = vector<int>(n, 1);
    }

    inline int get(int x) {
        if (p[x] == x) {
            return x;
        } else {
            return p[x] = get(p[x]);
        }
    }

    inline bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) {
            return false;
        }
        p[x] = y;
        sz[y] += sz[x];
        return true;
    }

    inline bool same(int x, int y) {
        return (get(x) == get(y));
    }

    inline int size(int x) {
        return sz[get(x)];
    }

    inline bool root(int x) {
        return (x == get(x));
    }
};

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
    dsu uf(n);
    for (int i = 0; i < r; i++) {
        if (x[i] == 2) {
            continue;
        }
        for (int j = a[i]; j <= b[i]; j++) {
            uf.unite(j, a[i]);
        }
    }
    string ans(n, '?');
    ans[0] = 'R';
    for (int i = 1; i < n; i++) {
        if (uf.same(i, i - 1)) {
            ans[i] = ans[i - 1];
        } else {
            ans[i] = ans[i - 1] ^ 'R' ^ 'B';
        }
    }
    for (int i = 0; i < r; i++) {
        if (x[i] == 1) {
            continue;
        }
        for (int j = a[i]; j < b[i]; j++) {
            if (!uf.same(j, j + 1)) {
                break;
            }
            if (j == b[i] - 1) {
                return 0;
            }
        }
    }
    craft(ans);
    return 1;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}
#endif

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