Submission #559572

#	Time	Username	Problem	Language	Result	Execution time	Memory
559572		nghiass001	Hexagonal Territory (APIO21_hexagon)	C++17	32 / 100	27 ms	15192 KiB

hexagon

#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
#define pii pair<int, int>
using namespace std;
const int N = 2e5 + 5, N3 = 2005, MOD = 1e9 + 7;
const int Gx[6] = {0, 1, 1, 0, -1, -1};
const int Gy[6] = {2, 1, -1, -2, -1, 1};

template <typename A>
long long add(A x) { return x % MOD; }
template <typename A, typename ...B>
long long add(A x, B ...y) { return (add(x) + add(y...)) % MOD; }
template <typename A>
long long multi(A x) { return x % MOD; }
template <typename A, typename ...B>
long long multi(A x, B ...y) { return multi(x) * multi(y...) % MOD; }

int n, A, B;
vector<int> D, L;
vector<int> Q[N * 2];

int sub12() {
    assert(L[0] == L[1] && L[1] == L[2]);
    long long num = L[0];
    long long cnode = multi(num + 1, num + 2, (MOD + 1) / 2);
    long long res = multi(cnode, A);
    res = add(res, multi(B, num, num + 1, num + 2, (MOD + 1) / 3));
    return res;
}

int cdepth[N3], num[N3 * 2][N3 * 2];
int sub3() {
    int x = N3, y = N3;
    int pre_dir = D.back();

    REP(i, 0, D.size()) {
        int dir = D[i];
        int count_dir = L[i];
        REP(j, 0, count_dir) {
            if (Gy[pre_dir] * Gy[dir] > 0) {
                Q[y].push_back(x);
            }
            else {
                Q[y].push_back(x);
                Q[y].push_back(x);
            }
            if (Gy[dir] / 2) {
                Q[y + Gy[dir] / 2].push_back(x);
            }

            num[x][y] = -1;
            x += Gx[dir];
            y += Gy[dir];
            pre_dir = dir;
        }
    }

    auto diff = [] (int x, int i) -> int {
        return (x^i)&1;
    };

    auto same = [] (int x, int i) -> int {
        return ((x^i)&1)^1;
    };

    REP(i, 0, N3 * 2) if (Q[i].size()) {
        sort(Q[i].begin(), Q[i].end());
        REP(j, 1, Q[i].size()) {
            if (Q[i][j] == Q[i][j - 1]) continue;
            if (j&1) {
                int x = Q[i][j] + diff(Q[i][j], i);
                int y = Q[i][j - 1] - diff(Q[i][j - 1], i);
                for(int w = y + 2; w < x; w += 2) num[w][i] = -1;
            }
        }
    }

    vector<pii> DQ;
    DQ.emplace_back(N3, N3);
    num[N3][N3] = 0;
    ++cdepth[0];
    REP(i, 0, DQ.size()) {
        x = DQ[i].first, y = DQ[i].second;
        REP(dir, 0, 6) {
            int u = x + Gx[dir];
            int v = y + Gy[dir];
            if (num[u][v] == -1) {
                num[u][v] = num[x][y] + 1;
                DQ.emplace_back(u, v);
                ++cdepth[num[u][v]];
            }
        }
    }

    long long res = 0;
    REP(i, 0, N3) {
        long long sl = cdepth[i];
        res = add(res, multi(sl, A), multi(sl, i, B));
    }
    return res;
}

int sub4() {
    int x = N, y = N;
    int pre_dir = D.back();

    REP(i, 0, D.size()) {
        int dir = D[i];
        int count_dir = L[i];
        REP(j, 0, count_dir) {
            if (Gy[pre_dir] * Gy[dir] > 0) {
                Q[y].push_back(x);
            }
            else {
                Q[y].push_back(x);
                Q[y].push_back(x);
            }
            if (Gy[dir] / 2) {
                Q[y + Gy[dir] / 2].push_back(x);
            }
            x += Gx[dir];
            y += Gy[dir];
            pre_dir = dir;
        }
    }

    auto diff = [] (int x, int i) -> int {
        return (x^i)&1;
    };

    auto same = [] (int x, int i) -> int {
        return ((x^i)&1)^1;
    };

    long long res = 0;
    REP(i, 0, N * 2) if (Q[i].size()) {
        sort(Q[i].begin(), Q[i].end());
        int sum = same(Q[i][0], i);
        REP(j, 1, Q[i].size()) {
            if (Q[i][j] == Q[i][j - 1]) continue;
            sum += same(Q[i][j], i);
            if (j&1) {
                int x = Q[i][j] + diff(Q[i][j], i);
                int y = Q[i][j - 1] - diff(Q[i][j - 1], i);
                if (x > y) sum += (x - y - 2) / 2;
            }
        }
        res = add(res, sum);
    }

    res = multi(res, A);
    return res;
}

int draw_territory(int N, int AA, int BB, vector<int> Dx, vector<int> Lx) {
    n = N; A = AA; B = BB; D = Dx; L = Lx;
    for(int &v : D) --v;
    int sz = 0; for(int v : L) sz += v;

    auto ask = [&] () -> int {
        if (N == 3) return sub12();
        if (sz <= 2000) return sub3();
        if (B == 0 && sz <= 200000) return sub4();
        return 0;
    };

    return ask();
}

Compilation message (stderr)

hexagon.cpp: In function 'int sub3()':
hexagon.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define REP(i,l,r) for(int i=(l); i<(r); ++i)
      |                                    ^
hexagon.cpp:39:5: note: in expansion of macro 'REP'
   39 |     REP(i, 0, D.size()) {
      |     ^~~
hexagon.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define REP(i,l,r) for(int i=(l); i<(r); ++i)
      |                                    ^
hexagon.cpp:71:9: note: in expansion of macro 'REP'
   71 |         REP(j, 1, Q[i].size()) {
      |         ^~~
hexagon.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define REP(i,l,r) for(int i=(l); i<(r); ++i)
      |                                    ^
hexagon.cpp:85:5: note: in expansion of macro 'REP'
   85 |     REP(i, 0, DQ.size()) {
      |     ^~~
hexagon.cpp:65:10: warning: variable 'same' set but not used [-Wunused-but-set-variable]
   65 |     auto same = [] (int x, int i) -> int {
      |          ^~~~
hexagon.cpp: In function 'int sub4()':
hexagon.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define REP(i,l,r) for(int i=(l); i<(r); ++i)
      |                                    ^
hexagon.cpp:110:5: note: in expansion of macro 'REP'
  110 |     REP(i, 0, D.size()) {
      |     ^~~
hexagon.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define REP(i,l,r) for(int i=(l); i<(r); ++i)
      |                                    ^
hexagon.cpp:142:9: note: in expansion of macro 'REP'
  142 |         REP(j, 1, Q[i].size()) {
      |         ^~~

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