oj.uz

Submission #951364

# Submission time Handle Problem Language Result Execution time Memory
951364 2024-03-21T17:19:40 Z Nhoksocqt1 Hexagonal Territory (APIO21_hexagon) C++17
20 / 100
 756 ms 48948 KB 
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 200005;
const int MOD = 1e9+7;

const int lx[] = {0, 1, 1, 0, -1, -1};
const int ly[] = {2, 1, -1, -2, -1, 1};

struct Move {
    int dir, len;
} p[MAXN];

ll costA, costB;
int dist[4010][8010], numMove;
bool dx[4010][8010], dxr[4010][8010];

inline ll C2(int n) {
    return 1LL * n * (n + 1) / 2 % MOD;
}

ll powermod(ll a, int exponent) {
    ll res(1);
    while(exponent > 0) {
        if(exponent & 1)
            res = res * a % MOD;

        a = a * a % MOD;
        exponent >>= 1;
    }

    return res;
}

int inv6 = powermod(6, MOD - 2);
inline ll T2(int n) {
    return 1LL * n * (n + 1) % MOD * (2 * n + 1) % MOD * inv6 % MOD;
}

int subn3(void) {
    assert(p[1].len == p[2].len && p[2].len == p[3].len);
    assert(p[2].dir == (p[1].dir + 1) % 6 + 1 && p[3].dir == (p[2].dir + 1) % 6 + 1 || p[1].dir == (p[2].dir + 1) % 6 + 1 && p[2].dir == (p[3].dir + 1) % 6 + 1);

    ll ans = C2(p[1].len + 1) * costA % MOD;
    ans = (ans - C2(p[1].len + 1) * costB % MOD + MOD) % MOD;
    ans = (ans + T2(p[1].len + 1) * costB) % MOD;
    return ans;
}

int sub3(void) {
    int x(2001), y(4002);
    dx[x][y] = 1;

    for (int i = 1; i <= numMove; ++i) {
        int len(p[i].len), dir(p[i].dir - 1);
        while(len--) {
            x += lx[dir], y += ly[dir];
            dx[x][y] = 1;
        }
    }

    queue<ii> qu;
    qu.push(ii(2001, 0));
    dxr[2001][0] = 1;

    while(sz(qu)) {
        int x(qu.front().fi), y(qu.front().se);
        qu.pop();

        for (int id = 0; id < 6; ++id) {
            int u(x + lx[id]), v(y + ly[id]);
            if(min(u, v) < 0 || u > 4002 || v > 8004 || dx[u][v] || dxr[u][v])
                continue;

            dxr[u][v] = 1;
            qu.push(ii(u, v));
        }
    }

    qu.push(ii(x, y));
    dist[x][y] = 1;

    while(sz(qu)) {
        int x(qu.front().fi), y(qu.front().se);
        qu.pop();

        for (int id = 0; id < 6; ++id) {
            int u(x + lx[id]), v(y + ly[id]);
            if(min(u, v) < 0 || u > 4002 || v > 8004 || dist[u][v] > 0 || dxr[u][v])
                continue;

            dist[u][v] = dist[x][y] + 1;
            qu.push(ii(u, v));
        }
    }

    ll res(0);
    int cntNodes(0);
    for (int i = 0; i <= 4002; ++i) {
        for (int j = 0; j <= 8004; ++j) {
            if(dist[i][j] > 0) {
                res = (res + (dist[i][j] - 1) * costB + costA) % MOD;
                ++cntNodes;
            }
        }
    }

    //cout << cntNodes << '\n';
    return res;
}

struct Point {
    int x, y;

    Point(int _x = 0, int _y = 0) : x(_x), y(_y) {};
} point[MAXN];

int subB0(void) {
    ll S(0), B(0);
    int x(0), y(0);
    point[0] = Point(x, y);
    for (int i = 1; i <= numMove; ++i) {
        int len(p[i].len), dir(p[i].dir - 1);
        x += lx[dir] * len;
        y += ly[dir] * len;
        point[i] = Point(x, y);
        B += len;
    }

    for (int i = 0; i < numMove; ++i)
        S += abs(1LL * (point[i + 1].y - point[i].y) * (point[i].x + point[i + 1].x));

    return ((S / 2 - B) / 2 + B + 1) % MOD * costA % MOD;
}

int draw_territory(int _N, int _A, int _B, vector<int> _D, vector<int> _L) {
    numMove = _N, costA = _A, costB = _B;

    int sumLen(0);
    for (int i = 1; i <= numMove; ++i) {
        p[i] = {_D[i - 1], _L[i - 1]};
        sumLen += p[i].len;
    }

    if(numMove == 3)
        return subn3();

    if(sumLen <= 2000)
        return sub3();

    //cout << "        " << sub3() << '\n';
    if(costB == 0)
        return subB0();
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "hexagon"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    vector<int> d, l;
    int n, a, b;
    cin >> n >> a >> b;

    d.resize(n), l.resize(n);
    for (int i = 0; i < n; ++i)
        cin >> d[i] >> l[i];

    int answer = draw_territory(n, a, b, d, l);
    cout << "ANSWER: " << answer << '\n';

    return 0;
}

#endif // Nhoksocqt1

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from hexagon.cpp:1:
hexagon.cpp: In function 'int subn3()':
hexagon.cpp:59:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   59 |     assert(p[2].dir == (p[1].dir + 1) % 6 + 1 && p[3].dir == (p[2].dir + 1) % 6 + 1 || p[1].dir == (p[2].dir + 1) % 6 + 1 && p[2].dir == (p[3].dir + 1) % 6 + 1);
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hexagon.cpp: In function 'int draw_territory(int, int, int, std::vector<int>, std::vector<int>)':
hexagon.cpp:171:1: warning: control reaches end of non-void function [-Wreturn-type]
  171 | }
      | ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 1 ms 6744 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 7000 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 1 ms 6748 KB Output is correct
12 Correct 1 ms 6744 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 41760 KB Output is correct
2 Correct 719 ms 45472 KB Output is correct
3 Correct 666 ms 44584 KB Output is correct
4 Correct 685 ms 44480 KB Output is correct
5 Correct 671 ms 47048 KB Output is correct
6 Correct 670 ms 44768 KB Output is correct
7 Correct 632 ms 44748 KB Output is correct
8 Correct 684 ms 44624 KB Output is correct
9 Correct 684 ms 42008 KB Output is correct
10 Correct 686 ms 42064 KB Output is correct
11 Correct 642 ms 41996 KB Output is correct
12 Correct 664 ms 48464 KB Output is correct
13 Correct 701 ms 48620 KB Output is correct
14 Correct 669 ms 48844 KB Output is correct
15 Correct 655 ms 41876 KB Output is correct
16 Correct 687 ms 44220 KB Output is correct
17 Correct 647 ms 41932 KB Output is correct
18 Correct 1 ms 6744 KB Output is correct
19 Correct 1 ms 6748 KB Output is correct
20 Correct 1 ms 7000 KB Output is correct

Subtask #4
0 / 12.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 41964 KB Output is correct
2 Correct 756 ms 45216 KB Output is correct
3 Correct 658 ms 44560 KB Output is correct
4 Correct 693 ms 44392 KB Output is correct
5 Correct 680 ms 47044 KB Output is correct
6 Correct 631 ms 44628 KB Output is correct
7 Correct 645 ms 44628 KB Output is correct
8 Correct 635 ms 44468 KB Output is correct
9 Correct 650 ms 42140 KB Output is correct
10 Correct 704 ms 42068 KB Output is correct
11 Correct 637 ms 42056 KB Output is correct
12 Correct 682 ms 48424 KB Output is correct
13 Correct 668 ms 48584 KB Output is correct
14 Correct 671 ms 48948 KB Output is correct
15 Correct 658 ms 41676 KB Output is correct
16 Correct 669 ms 44376 KB Output is correct
17 Correct 709 ms 41808 KB Output is correct
18 Incorrect 1 ms 6748 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

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

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 41920 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 733 ms 45416 KB Output is correct
7 Correct 631 ms 44444 KB Output is correct
8 Correct 694 ms 44372 KB Output is correct
9 Correct 632 ms 46948 KB Output is correct
10 Correct 655 ms 44760 KB Output is correct
11 Correct 657 ms 44752 KB Output is correct
12 Correct 658 ms 44368 KB Output is correct
13 Correct 729 ms 41936 KB Output is correct
14 Correct 686 ms 42088 KB Output is correct
15 Correct 666 ms 42124 KB Output is correct
16 Correct 713 ms 48588 KB Output is correct
17 Correct 664 ms 48664 KB Output is correct
18 Correct 627 ms 48844 KB Output is correct
19 Correct 683 ms 41884 KB Output is correct
20 Correct 637 ms 44308 KB Output is correct
21 Correct 658 ms 42064 KB Output is correct
22 Incorrect 1 ms 6748 KB Output isn't correct
23 Halted 0 ms 0 KB -