oj.uz

Submission #951363

# Submission time Handle Problem Language Result Execution time Memory
951363 2024-03-21T17:17:37 Z Nhoksocqt1 Hexagonal Territory (APIO21_hexagon) C++17
20 / 100
 716 ms 48936 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) * 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();

    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:170:1: warning: control reaches end of non-void function [-Wreturn-type]
  170 | }
      | ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 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 Correct 1 ms 6744 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 2 ms 7004 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 1 ms 6776 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 1 ms 6772 KB Output is correct
10 Correct 1 ms 7024 KB Output is correct
11 Correct 1 ms 6748 KB Output is correct
12 Correct 1 ms 6748 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 41776 KB Output is correct
2 Correct 660 ms 45256 KB Output is correct
3 Correct 705 ms 44496 KB Output is correct
4 Correct 643 ms 44372 KB Output is correct
5 Correct 640 ms 47248 KB Output is correct
6 Correct 635 ms 44840 KB Output is correct
7 Correct 636 ms 44748 KB Output is correct
8 Correct 632 ms 44368 KB Output is correct
9 Correct 687 ms 41852 KB Output is correct
10 Correct 676 ms 42040 KB Output is correct
11 Correct 665 ms 42216 KB Output is correct
12 Correct 668 ms 48640 KB Output is correct
13 Correct 683 ms 48788 KB Output is correct
14 Correct 670 ms 48936 KB Output is correct
15 Correct 645 ms 41696 KB Output is correct
16 Correct 669 ms 44444 KB Output is correct
17 Correct 661 ms 41940 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 1 ms 6772 KB Output is correct
20 Correct 2 ms 6744 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6748 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 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Incorrect 2 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 643 ms 41788 KB Output is correct
2 Correct 658 ms 45260 KB Output is correct
3 Correct 645 ms 44752 KB Output is correct
4 Correct 660 ms 44492 KB Output is correct
5 Correct 670 ms 47052 KB Output is correct
6 Correct 672 ms 44752 KB Output is correct
7 Correct 677 ms 44716 KB Output is correct
8 Correct 673 ms 44536 KB Output is correct
9 Correct 716 ms 41972 KB Output is correct
10 Correct 666 ms 42188 KB Output is correct
11 Correct 636 ms 42068 KB Output is correct
12 Correct 649 ms 48356 KB Output is correct
13 Correct 645 ms 48716 KB Output is correct
14 Correct 704 ms 48848 KB Output is correct
15 Correct 653 ms 41812 KB Output is correct
16 Correct 692 ms 44116 KB Output is correct
17 Correct 711 ms 41756 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 6744 KB Output is correct
2 Correct 1 ms 6744 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 647 ms 41888 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 Correct 1 ms 6748 KB Output is correct
6 Correct 684 ms 45384 KB Output is correct
7 Correct 695 ms 44368 KB Output is correct
8 Correct 629 ms 44368 KB Output is correct
9 Correct 669 ms 47312 KB Output is correct
10 Correct 654 ms 44928 KB Output is correct
11 Correct 638 ms 44748 KB Output is correct
12 Correct 684 ms 44504 KB Output is correct
13 Correct 658 ms 41956 KB Output is correct
14 Correct 631 ms 41992 KB Output is correct
15 Correct 665 ms 41932 KB Output is correct
16 Correct 659 ms 48440 KB Output is correct
17 Correct 681 ms 48468 KB Output is correct
18 Correct 675 ms 48844 KB Output is correct
19 Correct 651 ms 41808 KB Output is correct
20 Correct 673 ms 44284 KB Output is correct
21 Correct 646 ms 42064 KB Output is correct
22 Incorrect 1 ms 6748 KB Output isn't correct
23 Halted 0 ms 0 KB -