oj.uz

Submission #425940

# Submission time Handle Problem Language Result Execution time Memory
425940 2021-06-13T12:28:41 Z ocarima Hexagonal Territory (APIO21_hexagon) C++14
0 / 100
 2000 ms 53448 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 5068 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2098 ms 5068 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 23020 KB Output is correct
2 Correct 270 ms 29680 KB Output is correct
3 Correct 258 ms 27688 KB Output is correct
4 Correct 269 ms 26264 KB Output is correct
5 Correct 259 ms 29556 KB Output is correct
6 Correct 252 ms 25740 KB Output is correct
7 Correct 259 ms 25992 KB Output is correct
8 Correct 255 ms 24192 KB Output is correct
9 Correct 268 ms 24000 KB Output is correct
10 Correct 252 ms 24288 KB Output is correct
11 Correct 269 ms 25048 KB Output is correct
12 Correct 258 ms 28100 KB Output is correct
13 Correct 263 ms 32324 KB Output is correct
14 Correct 270 ms 32616 KB Output is correct
15 Correct 261 ms 27332 KB Output is correct
16 Correct 289 ms 23892 KB Output is correct
17 Correct 257 ms 24644 KB Output is correct
18 Incorrect 279 ms 35308 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 313 ms 53448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2098 ms 5068 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 23092 KB Output is correct
2 Correct 259 ms 29676 KB Output is correct
3 Correct 290 ms 27876 KB Output is correct
4 Correct 262 ms 26168 KB Output is correct
5 Correct 280 ms 29544 KB Output is correct
6 Correct 305 ms 25640 KB Output is correct
7 Correct 237 ms 25924 KB Output is correct
8 Correct 261 ms 24232 KB Output is correct
9 Correct 255 ms 24132 KB Output is correct
10 Correct 250 ms 24292 KB Output is correct
11 Correct 269 ms 25044 KB Output is correct
12 Correct 265 ms 28084 KB Output is correct
13 Correct 261 ms 32324 KB Output is correct
14 Correct 271 ms 32548 KB Output is correct
15 Correct 247 ms 27104 KB Output is correct
16 Correct 266 ms 23800 KB Output is correct
17 Correct 251 ms 24808 KB Output is correct
18 Incorrect 322 ms 53416 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2096 ms 5068 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 23084 KB Output is correct
2 Execution timed out 2072 ms 5068 KB Time limit exceeded
3 Halted 0 ms 0 KB -