Submission #425940

#	Time	Username	Problem	Language	Result	Execution time	Memory
425940		ocarima	Hexagonal Territory (APIO21_hexagon)	C++14	0 / 100	2098 ms	53448 KiB

hexagon

#include "hexagon.h"
#include <vector>
#include<bits/stdc++.h>

using namespace std;

#define nl "\n"
#define debugsl(x) cout << #x << " = " << x << ", "
#define debug(x) debugsl(x) << nl

#define lli long long
#define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
#define repa(i, a, b) for(lli i = (a); i >= (b); --i)

#define MAX_N 1200
#define MOD 1000000007

lli mat[2][MAX_N][MAX_N], frontera[2][MAX_N][MAX_N], llenado[2][MAX_N][MAX_N];
lli pmat, pfil, pcol;


bool sigpos(lli &matriz, lli &fila, lli &columna, lli dir){
    if (dir == 1){
        if (!fila) return false;
        --fila;
    }
    else if (dir == 2){
        if (!matriz && !fila) return false;
        if (!matriz) --fila;
        else ++columna;
        matriz ^= 1;
    }
    else if (dir == 3){
        if (matriz && (fila == MAX_N - 1 || columna == MAX_N - 1)) return false;
        if (matriz){ ++fila; ++columna; }
        matriz ^= 1;
    }
    else if (dir == 4){
        if (fila == MAX_N - 1) return false;
        ++fila;
    }
    else if (dir == 5){
        if ((!matriz && !columna) || (matriz && fila == MAX_N - 1)) return false;
        if (!matriz) --columna;
        else ++fila;
        matriz ^= 1;
    }
    else if (dir == 6){
        if (!matriz && (!fila || !columna)) return false;
        if (!matriz){ --fila; --columna; }
        matriz ^= 1;
    }
    return true;
}

bool llena(lli m, lli f, lli c){
    lli sm, sf, sc, cm, cf, cc;
    queue<lli> qm, qf, qc;
    bool res = false;

    qm.push(m);
    qf.push(f);
    qc.push(c);
    llenado[m][f][c] = 1;

    while (!qm.empty()){
        cm = qm.front(); qm.pop();
        cf = qf.front(); qf.pop();
        cc = qc.front(); qc.pop();

        rep(dir, 1, 6){
            sm = cm; sf = cf; sc = cc;
            if (!sigpos(sm, sf, sc, dir)) { res = true; continue; }
            if (!llenado[sm][sf][sc] && !frontera[sm][sf][sc]){
                llenado[sm][sf][sc] = 1;
                qm.push(sm);
                qf.push(sf);
                qc.push(sc);
            }
        }
    }

    return res;
}

int draw_territory(int N, int A, int B,
                   std::vector<int> D, std::vector<int> L) {


    pmat = 0; pfil = MAX_N >> 1; pcol = MAX_N >> 1;

    frontera[pmat][pfil][pcol] = 1;
    rep(i, 0, N - 1){
        rep(j, 1, L[i]){
            sigpos(pmat, pfil, pcol, D[i]);
            frontera[pmat][pfil][pcol] = 1;
        }
    }

    // ENCUENTRA EL EXTERIOR;
    rep(dir, 1, 6){
        pmat = 0; pfil = MAX_N >> 1; pcol = MAX_N >> 1;
        sigpos(pmat, pfil, pcol, dir);
        if (!frontera[pmat][pfil][pcol]){
            // HAZ EL FILL
            if (llena(pmat, pfil, pcol)) break;

            // LIMPIA EL LLENADO
            rep(m, 0, 1) rep(f, 0, MAX_N - 1) rep(c, 0, MAX_N - 1) llenado[m][f][c] = 0;
        }
    }

    lli sm, sf, sc, cm, cf, cc, res, dis;
    queue<lli> qm, qf, qc, qd;

    res = 0;
    qm.push(0);
    qf.push(MAX_N >> 1);
    qc.push(MAX_N >> 1);
    qd.push(0);
    mat[0][MAX_N >> 1][MAX_N >> 1] = 1;

    while (!qm.empty()){
        cm = qm.front(); qm.pop();
        cf = qf.front(); qf.pop();
        cc = qc.front(); qc.pop();
        dis = qd.front(); qd.pop();

        res += A + ((B * dis) % MOD);
        res %= MOD;

        rep(dir, 1, 6){
            sm = cm; sf = cf; sc = cc;
            sigpos(sm, sf, sc, dir);

            // SI NO ES PARTE EXTERNA O ES FRONTERA Y NO ESTA VISITADA, CUENTALO
            if (!mat[sm][sf][sc] && (!llenado[sm][sf][sc] || frontera[sm][sf][sc])){
                mat[sm][sf][sc] = 1; // VISITALA
                qm.push(sm);
                qf.push(sf);
                qc.push(sc);
                qd.push(dis + 1);
            }
        }
    }

    return res;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 15
• Subtask 6: 0 / 19
• Subtask 7: 0 / 18
• Subtask 8: 0 / 16