Submission #1245440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245440		BlockOG	Building Skyscrapers (CEOI19_skyscrapers)	C++20	8 / 100	3595 ms	7152 KiB

skyscrapers

#include <bits/stdc++.h>

// mrrrow meeow :3
// go play vivid/stasis now! it's free on steam

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;

int ____init = [] {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

struct Node {
    int xl = 2000000000, yl = 2000000000;
    int xr = 2000000000, yr = 2000000000;
    bool active = false;

    Node combine(const Node &r) const {
        const Node &l = *this;
        if (l.active && !r.active) return l;
        if (!l.active && r.active) return r;
        if (!l.active && !r.active) return Node();

        Node res;

        res.active = true;
        res.xl = min(l.xl, r.xl);
        res.yl = min(l.yl, r.yl);
        res.xr = max(l.xr, r.xr);
        res.yr = max(l.yr, r.yr);

        return res;
    }
};

int n;
const int N = 1 << 18;
Node st[N * 2];

void st_set(int i, bool v) {
    i += N;
    st[i].active = v;
    for (i /= 2; i > 0; i /= 2) st[i] = st[i * 2].combine(st[i * 2 + 1]);
}

set<pair<int, int>> sk;

int l = 0;
int order[150000];

set<pair<int, int>> been;
bool dfs(int x, int y) {
    if (x < st[1].xl || st[1].xr < x || y < st[1].yl || st[1].yr < y) return true;
    if (been.count({x, y}) || sk.count({x, y})) return false;
    been.insert({x, y});

    if (dfs(x - 1, y)) return true;
    if (dfs(x + 1, y)) return true;
    if (dfs(x, y - 1)) return true;
    if (dfs(x, y + 1)) return true;

    return false;
}

bool backtrack() {
    if (l == n) return true;

    l++;
    fo(i, 0, n) {
        if (st[N + i].active) continue;

        if (l == 1) goto yes;

        fo(dx, -1, 2) {
            fo(dy, -1, 2) {
                if (dx == 0 && dy == 0) continue;
                if (sk.count({st[N + i].xl + dx, st[N + i].yl + dy})) goto yes;
            }
        }
        continue;
    yes:;

        been.clear();
        if (!dfs(st[N + i].xl, st[N + i].yl)) continue;

        order[l - 1] = i;
        st_set(i, true);
        sk.insert({st[N + i].xl, st[N + i].yl});
        if (backtrack()) return true;
        sk.erase({st[N + i].xl, st[N + i].yl});
        st_set(i, false);
    }
    l--;

    return false;
}

int main() {
    int t;
    cin >> n >> t;
    fo(i, 0, n) {
        cin >> st[N + i].xl >> st[N + i].yl;
        st[N + i].xr = st[N + i].xl, st[N + i].yr = st[N + i].yl;
    }
    of(i, 1, N) st[i] = st[i * 2].combine(st[i * 2 + 1]);

    if (backtrack()) {
        cout << "YES" << endl;
        fo(i, 0, l) cout << order[i] + 1 << endl;
    } else cout << "NO" << endl;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 12
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 10
• Subtask 7: 0 / 19