Submission #563569

#	Time	Username	Problem	Language	Result	Execution time	Memory
563569		balbit	Building Skyscrapers (CEOI19_skyscrapers)	C++14	100 / 100	3130 ms	214264 KiB

skyscrapers

#include <bits/stdc++.h>
//#define int ll
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 150000+5;

bool full[maxn*9]; // is the block at this index full
bool canout[maxn]; // can be connected to the outside!
int id[maxn*9];
int X[maxn*9], Y[maxn*9]; // coordinates of this
vector<int> adj[maxn*9];
vector<int> adj4[maxn*9];
// adj blocks in clockwise order starting from <0, 1>
int par[maxn*9];
vector<int> here[maxn*9];

//int NOWROUND=-1;
//int lasttouch[maxn*9];

const vector<pii> DIR = {{0,1}, {1,1}, {1,0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
const vector<pii> D4 = {{0,1}, {1,0}, {0, -1}, {-1, 0}};

int find(int x) {return par[x] == x? x : par[x] = find(par[x]);}

void ASS(bool x) {
    if (!x) {
        cout<<"BRUH"<<endl; exit(0);
    }
}

int NOWOUT; // head of the outside

bool ISAP(int at) {
    static bool TMP[8];
    bug(at, full[at]);
    ASS(full[at]);
    int totfull = 0;
    vector<int>FND(4);
    REP(j, 8) {
        totfull += (TMP[j] = full[adj[at][j]]);
        if (j%2==0) {
            FND[j/2] = find(adj[at][j]);
        }
    }
    if (totfull > 1) {
        REP(i,4) {
            if (FND[i] == FND[(i+1)&3]) {
                if (TMP[i*2+1]) {
                    // found!
                    return 1;
                }
            }
        }
    }else return 0;
    // case 2: the equal zones wrap around
    if (FND[0] == FND[2]) {
        int r = TMP[1]+TMP[2]+TMP[3];
        if (r && r != totfull) return 1;
    }
    if (FND[1] == FND[3]) {
        int r = TMP[4]+TMP[5]+TMP[3];
        if (r && r != totfull) return 1;
    }
    return 0;
}

set<int>canrem;

bool inset[maxn*9];

bool markedtodo[maxn];
vector<int> todo;

inline void RUN(int x) {
    if (!canout[x] || !full[x]) return;
    bool shouldbein = !ISAP(x);
    if (inset[x] != shouldbein) {
        if (shouldbein) {
            canrem.insert(x);
            inset[x] = 1;
        }else{
            canrem.erase(x);
            inset[x] = 0;
        }
    }
}

inline void UPD(int x) {
    if (markedtodo[x] || !full[x]) return;
    markedtodo[x] = 1;
    todo.pb(x);
}

void GOGO(){
    for (int x : todo) {
        RUN(x); markedtodo[x] = 0;
    }
    todo.clear();
}

void markout(vector<int> &v) {
    for (int x : v) {
        for (int y : adj4[x]) {
            if (full[y] && !canout[y]) {
                canout[y] = 1;
                UPD(y);
            }
        }
    }
}


void mrg(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    if (SZ(here[a]) > SZ(here[b])) swap(a,b);
    if (a == NOWOUT) swap(a,b);
    if (b == NOWOUT) {
        markout(here[a]);
    }
    par[a] = b;
    here[b].insert(here[b].end(), ALL(here[a]));
//    vector<int> todo;
    for (int x : here[a]) {
        for (int y : adj4[x]) {
            if (full[y]) {
                UPD(y);
            }
        }
    }
//    SORT_UNIQUE(todo);
//    for (int x : todo) {
//        UPD(x);
//    }
    vector<int> () .swap(here[a]);
}

void mrg1(int a, int b) {
    a = find(a); b = find(b);
    if (SZ(here[a]) > SZ(here[b])) swap(a,b);
    par[a] = b;
    here[b].insert(here[b].end(), ALL(here[a]));
    vector<int> () .swap(here[a]);
}

vector<int> ret;

void rem(int at) {
    bug("removing", at, full[at]);
    ASS(full[at]);
    // this shouldn't be an AP
    full[at] = 0;
    ret.pb(at);
    for (int i = 0; i<8; i+=2) {
        if (!full[adj[at][i]]) mrg(at, adj[at][i]);
    }
    bug(SZ(todo));
    for (int x : adj[at]) {
        if (full[x]) UPD(x);
    }
    GOGO();
}

signed main(){
    IOS();

    map<pii, int> mp;
    int n; cin>>n;
    int subt; cin>>subt;

    REP(i,n) {
        cin>>X[i]>>Y[i];
        mp[{X[i], Y[i]}] = i;
        full[i] = 1;
    }

    int IT = SZ(mp);



    REP(i, n*9) {
        par[i] = i;
    }
    REP(i,n) {
        here[i].pb(i);
    }

    REP(i,n) {

        for (auto pp : DIR) {
            int j = pp.f, k = pp.s;
            pii P = {X[i] + j, Y[i] + k};
            if (!mp.count(P)) {
                tie(X[IT], Y[IT]) = P;
                mp[P] = IT++;
            }
            adj[i].pb(mp[P]);
            if (abs(j) + abs(k) == 1) {
                adj4[i].pb(mp[P]);
            }
        }

        for (int x : adj[i]) {
            if (full[x]) {
                mrg1(x, i);
            }
        }
    }

    REP(i,n) {
        if (find(i) != find(0)) {
            // death!
            cout<<"NO"<<endl;
            return 0;
        }
    }

    ASS(SZ(mp) == IT);

    REP(i,IT) {
        here[i] = {i};
        par[i] = i;
    }

    for (int i = n; i<IT; ++i) {
        for (auto pp : DIR) {
            int j = pp.f, k = pp.s;
            pii P = {X[i] + j, Y[i] + k};
            if (mp.count(P)) {
                adj[i].pb(mp[P]);
            }
        }
        for (auto pp : D4) {
            int j = pp.f, k = pp.s;
            pii P = {X[i] + j, Y[i] + k};
            if (mp.count(P)) {
                int to = mp[P];
                adj4[i].pb(to);
            }
        }
    }
    NOWOUT = mp.begin()->s;
    bug(X[NOWOUT], Y[NOWOUT]);
    ASS(!full[NOWOUT]);
    markout(here[NOWOUT]);

    for (int i = n; i<IT; ++i) {
        for (int to : adj4[i]) {
            if (!full[to]) {
                mrg(i, to);
            }
        }
    }

    GOGO();
//    for (int e : here[NOWOUT]) {
//        bug(e);
//    }
//    REP(i,IT) {
//        bug(i, X[i], Y[i], full[i]);
//        bug(find(i), canout[i]);
//    }

    REP(round, n) {
//        NOWROUND = round;
        #ifdef BALBIT
        bug(round);
        for (int x : canrem) cout<<x<<' ';
        cout<<endl;
        #endif // BALBIT
        if (SZ(canrem) == 0) {
            cout<<"DIE "<<round<<endl;
            return 0;
        }
        int e = *prev(canrem.end());
        canrem.erase(e);
        inset[e] = 0;
        rem(e);
    }

    cout<<"YES"<<endl;
    reverse(ALL(ret));
    for (int x : ret) cout<<x+1<<endl;

}

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