oj.uz

Submission #951367

# Submission time Handle Problem Language Result Execution time Memory
951367 2024-03-21T17:34:39 Z Nhoksocqt1 Hexagonal Territory (APIO21_hexagon) C++17
47 / 100
 709 ms 49008 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;

    //cout << x - 2001 << ' '<< y - 4002 << '\n';
    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;
        }

        //cout << x - 2001 << ' '<< y - 4002 << '\n';
    }

    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 += (1LL * point[i].x * point[i + 1].y - 1LL * point[i].y * point[i + 1].x);

    S = abs(S);
    //cout << S << ' ' << S / 2 << ' ' << B << ' ' << ((S / 4 - B) / 2 + B + 1) << '\n';
    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:176:1: warning: control reaches end of non-void function [-Wreturn-type]
  176 | }
      | ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 4 ms 6744 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 1 ms 6748 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 3 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 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 7000 KB Output is correct
8 Correct 2 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 6748 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 41716 KB Output is correct
2 Correct 680 ms 45428 KB Output is correct
3 Correct 683 ms 44592 KB Output is correct
4 Correct 656 ms 44368 KB Output is correct
5 Correct 685 ms 46984 KB Output is correct
6 Correct 664 ms 44748 KB Output is correct
7 Correct 671 ms 44824 KB Output is correct
8 Correct 658 ms 44632 KB Output is correct
9 Correct 691 ms 41968 KB Output is correct
10 Correct 667 ms 41916 KB Output is correct
11 Correct 631 ms 42064 KB Output is correct
12 Correct 647 ms 48328 KB Output is correct
13 Correct 680 ms 48544 KB Output is correct
14 Correct 647 ms 49008 KB Output is correct
15 Correct 636 ms 41688 KB Output is correct
16 Correct 635 ms 44148 KB Output is correct
17 Correct 685 ms 41932 KB Output is correct
18 Correct 1 ms 6748 KB Output is correct
19 Correct 1 ms 6748 KB Output is correct
20 Correct 1 ms 6900 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6832 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 6 ms 7260 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 8 ms 7516 KB Output is correct
12 Correct 8 ms 7616 KB Output is correct
13 Correct 7 ms 7516 KB Output is correct
14 Correct 8 ms 7772 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 2 ms 6760 KB Output is correct
17 Correct 2 ms 7004 KB Output is correct
18 Correct 1 ms 6748 KB Output is correct
19 Correct 1 ms 6748 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 5 ms 7260 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 1 ms 6744 KB Output is correct
12 Correct 1 ms 6744 KB Output is correct
13 Correct 7 ms 7612 KB Output is correct
14 Correct 8 ms 7504 KB Output is correct
15 Correct 7 ms 7512 KB Output is correct
16 Correct 8 ms 7764 KB Output is correct
17 Correct 2 ms 6748 KB Output is correct
18 Correct 1 ms 6748 KB Output is correct
19 Correct 1 ms 6748 KB Output is correct
20 Correct 12 ms 8540 KB Output is correct
21 Correct 2 ms 6748 KB Output is correct
22 Correct 2 ms 6744 KB Output is correct
23 Correct 16 ms 9052 KB Output is correct
24 Correct 25 ms 11100 KB Output is correct
25 Correct 26 ms 11260 KB Output is correct
26 Correct 14 ms 8796 KB Output is correct
27 Correct 10 ms 8024 KB Output is correct
28 Correct 8 ms 7772 KB Output is correct
29 Correct 38 ms 11860 KB Output is correct
30 Correct 28 ms 11860 KB Output is correct
31 Correct 29 ms 11864 KB Output is correct
32 Correct 28 ms 11604 KB Output is correct
33 Correct 14 ms 8536 KB Output is correct
34 Correct 8 ms 7772 KB Output is correct
35 Correct 1 ms 6748 KB Output is correct
36 Correct 1 ms 6748 KB Output is correct
37 Correct 1 ms 6744 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 641 ms 41924 KB Output is correct
2 Correct 627 ms 45356 KB Output is correct
3 Correct 628 ms 44428 KB Output is correct
4 Correct 669 ms 44516 KB Output is correct
5 Correct 640 ms 47052 KB Output is correct
6 Correct 682 ms 44692 KB Output is correct
7 Correct 709 ms 44748 KB Output is correct
8 Correct 651 ms 44612 KB Output is correct
9 Correct 637 ms 41808 KB Output is correct
10 Correct 645 ms 41864 KB Output is correct
11 Correct 651 ms 42040 KB Output is correct
12 Correct 650 ms 48464 KB Output is correct
13 Correct 662 ms 48768 KB Output is correct
14 Correct 645 ms 48844 KB Output is correct
15 Correct 699 ms 41744 KB Output is correct
16 Correct 677 ms 44332 KB Output is correct
17 Correct 668 ms 41928 KB Output is correct
18 Correct 1 ms 6744 KB Output is correct
19 Correct 2 ms 6748 KB Output is correct
20 Correct 2 ms 6748 KB Output is correct
21 Correct 2 ms 6748 KB Output is correct
22 Correct 2 ms 6748 KB Output is correct
23 Correct 2 ms 6748 KB Output is correct
24 Correct 6 ms 7260 KB Output is correct
25 Correct 1 ms 6748 KB Output is correct
26 Correct 1 ms 6748 KB Output is correct
27 Correct 1 ms 6776 KB Output is correct
28 Correct 7 ms 7516 KB Output is correct
29 Correct 7 ms 7552 KB Output is correct
30 Correct 7 ms 7516 KB Output is correct
31 Correct 8 ms 7772 KB Output is correct
32 Correct 2 ms 6748 KB Output is correct
33 Correct 1 ms 6748 KB Output is correct
34 Incorrect 1 ms 6768 KB Output isn't correct
35 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6744 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 629 ms 41704 KB Output is correct
2 Correct 2 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 Correct 1 ms 6744 KB Output is correct
6 Correct 638 ms 45416 KB Output is correct
7 Correct 651 ms 44696 KB Output is correct
8 Correct 638 ms 44824 KB Output is correct
9 Correct 642 ms 47184 KB Output is correct
10 Correct 664 ms 44712 KB Output is correct
11 Correct 680 ms 44632 KB Output is correct
12 Correct 659 ms 44500 KB Output is correct
13 Correct 672 ms 41924 KB Output is correct
14 Correct 684 ms 42072 KB Output is correct
15 Correct 680 ms 42064 KB Output is correct
16 Correct 675 ms 48332 KB Output is correct
17 Correct 692 ms 48460 KB Output is correct
18 Correct 650 ms 48760 KB Output is correct
19 Correct 686 ms 41988 KB Output is correct
20 Correct 664 ms 44240 KB Output is correct
21 Correct 624 ms 41900 KB Output is correct
22 Correct 1 ms 6748 KB Output is correct
23 Correct 2 ms 6748 KB Output is correct
24 Correct 2 ms 6748 KB Output is correct
25 Correct 2 ms 6748 KB Output is correct
26 Correct 2 ms 6748 KB Output is correct
27 Correct 2 ms 6748 KB Output is correct
28 Correct 7 ms 7296 KB Output is correct
29 Correct 2 ms 6748 KB Output is correct
30 Correct 1 ms 6748 KB Output is correct
31 Correct 1 ms 6584 KB Output is correct
32 Correct 8 ms 7516 KB Output is correct
33 Correct 7 ms 7620 KB Output is correct
34 Correct 8 ms 7516 KB Output is correct
35 Correct 10 ms 7772 KB Output is correct
36 Correct 2 ms 6796 KB Output is correct
37 Correct 2 ms 6748 KB Output is correct
38 Correct 1 ms 6748 KB Output is correct
39 Correct 12 ms 8540 KB Output is correct
40 Correct 3 ms 6748 KB Output is correct
41 Correct 2 ms 6748 KB Output is correct
42 Correct 16 ms 9052 KB Output is correct
43 Correct 25 ms 10924 KB Output is correct
44 Correct 26 ms 11356 KB Output is correct
45 Correct 15 ms 8796 KB Output is correct
46 Correct 10 ms 8008 KB Output is correct
47 Correct 7 ms 7772 KB Output is correct
48 Correct 28 ms 11912 KB Output is correct
49 Correct 29 ms 11660 KB Output is correct
50 Correct 32 ms 11860 KB Output is correct
51 Correct 28 ms 11604 KB Output is correct
52 Correct 14 ms 8536 KB Output is correct
53 Correct 8 ms 8024 KB Output is correct
54 Incorrect 1 ms 6748 KB Output isn't correct
55 Halted 0 ms 0 KB -