oj.uz

Submission #559572

# Submission time Handle Problem Language Result Execution time Memory
559572 2022-05-10T08:20:39 Z nghiass001 Hexagonal Territory (APIO21_hexagon) C++17
32 / 100
 27 ms 15192 KB 
#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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9696 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9700 KB Output is correct
5 Correct 6 ms 9616 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9656 KB Output is correct
2 Correct 6 ms 9660 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 8 ms 9708 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 7 ms 9684 KB Output is correct
8 Correct 6 ms 9704 KB Output is correct
9 Correct 7 ms 9684 KB Output is correct
10 Correct 7 ms 9684 KB Output is correct
11 Correct 8 ms 9704 KB Output is correct
12 Correct 8 ms 9704 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 8 ms 12264 KB Output is correct
3 Correct 7 ms 11092 KB Output is correct
4 Correct 7 ms 10720 KB Output is correct
5 Correct 8 ms 11220 KB Output is correct
6 Correct 7 ms 10580 KB Output is correct
7 Correct 7 ms 10984 KB Output is correct
8 Correct 7 ms 10452 KB Output is correct
9 Correct 6 ms 9940 KB Output is correct
10 Correct 7 ms 10068 KB Output is correct
11 Correct 7 ms 10360 KB Output is correct
12 Correct 14 ms 14824 KB Output is correct
13 Correct 11 ms 13900 KB Output is correct
14 Correct 12 ms 15192 KB Output is correct
15 Correct 8 ms 9812 KB Output is correct
16 Correct 7 ms 10212 KB Output is correct
17 Correct 7 ms 9828 KB Output is correct
18 Correct 6 ms 9684 KB Output is correct
19 Correct 6 ms 9684 KB Output is correct
20 Correct 6 ms 9684 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 14932 KB Output is correct
2 Correct 12 ms 10864 KB Output is correct
3 Correct 14 ms 11000 KB Output is correct
4 Correct 12 ms 10828 KB Output is correct
5 Correct 19 ms 11360 KB Output is correct
6 Correct 17 ms 11620 KB Output is correct
7 Correct 24 ms 11476 KB Output is correct
8 Correct 15 ms 11220 KB Output is correct
9 Correct 15 ms 11348 KB Output is correct
10 Correct 13 ms 11236 KB Output is correct
11 Correct 27 ms 13652 KB Output is correct
12 Correct 23 ms 14164 KB Output is correct
13 Correct 25 ms 14028 KB Output is correct
14 Correct 25 ms 13168 KB Output is correct
15 Correct 23 ms 11908 KB Output is correct
16 Correct 12 ms 10708 KB Output is correct
17 Correct 7 ms 9704 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Correct 5 ms 9704 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9660 KB Output is correct
3 Correct 20 ms 14916 KB Output is correct
4 Correct 13 ms 10864 KB Output is correct
5 Correct 12 ms 10964 KB Output is correct
6 Correct 11 ms 10728 KB Output is correct
7 Correct 15 ms 11252 KB Output is correct
8 Correct 17 ms 11604 KB Output is correct
9 Correct 19 ms 11484 KB Output is correct
10 Correct 11 ms 11220 KB Output is correct
11 Correct 14 ms 11496 KB Output is correct
12 Correct 12 ms 11324 KB Output is correct
13 Correct 26 ms 13652 KB Output is correct
14 Correct 24 ms 14188 KB Output is correct
15 Correct 23 ms 14048 KB Output is correct
16 Correct 25 ms 13156 KB Output is correct
17 Correct 17 ms 11860 KB Output is correct
18 Correct 11 ms 10708 KB Output is correct
19 Incorrect 5 ms 9704 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9708 KB Output is correct
2 Correct 11 ms 12240 KB Output is correct
3 Correct 7 ms 11012 KB Output is correct
4 Correct 7 ms 10728 KB Output is correct
5 Correct 6 ms 11220 KB Output is correct
6 Correct 7 ms 10580 KB Output is correct
7 Correct 7 ms 10992 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 6 ms 9944 KB Output is correct
10 Correct 6 ms 10068 KB Output is correct
11 Correct 6 ms 10324 KB Output is correct
12 Correct 11 ms 14808 KB Output is correct
13 Correct 10 ms 13900 KB Output is correct
14 Correct 12 ms 15192 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 6 ms 10196 KB Output is correct
17 Correct 6 ms 9828 KB Output is correct
18 Correct 22 ms 14896 KB Output is correct
19 Correct 13 ms 10872 KB Output is correct
20 Correct 13 ms 10988 KB Output is correct
21 Correct 11 ms 10708 KB Output is correct
22 Correct 16 ms 11304 KB Output is correct
23 Correct 17 ms 11632 KB Output is correct
24 Correct 17 ms 11504 KB Output is correct
25 Correct 12 ms 11240 KB Output is correct
26 Correct 13 ms 11348 KB Output is correct
27 Correct 13 ms 11220 KB Output is correct
28 Correct 27 ms 13620 KB Output is correct
29 Correct 24 ms 14188 KB Output is correct
30 Correct 24 ms 14184 KB Output is correct
31 Correct 25 ms 13168 KB Output is correct
32 Correct 18 ms 11860 KB Output is correct
33 Correct 10 ms 10728 KB Output is correct
34 Incorrect 6 ms 9704 KB Output isn't correct
35 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9592 KB Output is correct
2 Correct 6 ms 9700 KB Output is correct
3 Correct 6 ms 9704 KB Output is correct
4 Correct 6 ms 9704 KB Output is correct
5 Incorrect 6 ms 9704 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9688 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 11 ms 12260 KB Output is correct
7 Correct 7 ms 11092 KB Output is correct
8 Correct 7 ms 10728 KB Output is correct
9 Correct 7 ms 11220 KB Output is correct
10 Correct 6 ms 10600 KB Output is correct
11 Correct 7 ms 11092 KB Output is correct
12 Correct 7 ms 10452 KB Output is correct
13 Correct 6 ms 9960 KB Output is correct
14 Correct 6 ms 10068 KB Output is correct
15 Correct 6 ms 10324 KB Output is correct
16 Correct 12 ms 14808 KB Output is correct
17 Correct 10 ms 13900 KB Output is correct
18 Correct 12 ms 15176 KB Output is correct
19 Correct 6 ms 9812 KB Output is correct
20 Correct 7 ms 10196 KB Output is correct
21 Correct 6 ms 9832 KB Output is correct
22 Correct 20 ms 15004 KB Output is correct
23 Correct 12 ms 10964 KB Output is correct
24 Correct 12 ms 10972 KB Output is correct
25 Correct 10 ms 10732 KB Output is correct
26 Correct 14 ms 11252 KB Output is correct
27 Correct 15 ms 11628 KB Output is correct
28 Correct 17 ms 11544 KB Output is correct
29 Correct 11 ms 11240 KB Output is correct
30 Correct 13 ms 11348 KB Output is correct
31 Correct 13 ms 11220 KB Output is correct
32 Correct 25 ms 13608 KB Output is correct
33 Correct 26 ms 14156 KB Output is correct
34 Correct 23 ms 14052 KB Output is correct
35 Correct 25 ms 13132 KB Output is correct
36 Correct 18 ms 11852 KB Output is correct
37 Correct 11 ms 10708 KB Output is correct
38 Incorrect 6 ms 9684 KB Output isn't correct
39 Halted 0 ms 0 KB -