oj.uz

Submission #951339

# Submission time Handle Problem Language Result Execution time Memory
951339 2024-03-21T15:49:51 Z Nhoksocqt1 Hexagonal Territory (APIO21_hexagon) C++17
20 / 100
 793 ms 292976 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);
    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;
        }
    }

    return res;
}

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();
}

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

Subtask #1
3.0 / 3.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 40316 KB Output is correct
2 Correct 632 ms 43860 KB Output is correct
3 Correct 720 ms 42876 KB Output is correct
4 Correct 638 ms 43048 KB Output is correct
5 Correct 660 ms 43348 KB Output is correct
6 Correct 634 ms 43188 KB Output is correct
7 Correct 662 ms 43184 KB Output is correct
8 Correct 666 ms 42652 KB Output is correct
9 Correct 662 ms 40612 KB Output is correct
10 Correct 717 ms 42404 KB Output is correct
11 Correct 685 ms 42668 KB Output is correct
12 Correct 708 ms 46772 KB Output is correct
13 Correct 660 ms 47124 KB Output is correct
14 Correct 645 ms 47424 KB Output is correct
15 Correct 678 ms 40328 KB Output is correct
16 Correct 664 ms 42384 KB Output is correct
17 Correct 708 ms 40228 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 202 ms 292884 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Runtime error 132 ms 292964 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 40272 KB Output is correct
2 Correct 728 ms 43692 KB Output is correct
3 Correct 640 ms 42812 KB Output is correct
4 Correct 697 ms 42932 KB Output is correct
5 Correct 659 ms 43400 KB Output is correct
6 Correct 635 ms 42928 KB Output is correct
7 Correct 659 ms 43088 KB Output is correct
8 Correct 744 ms 42764 KB Output is correct
9 Correct 708 ms 40272 KB Output is correct
10 Correct 668 ms 42408 KB Output is correct
11 Correct 635 ms 42836 KB Output is correct
12 Correct 695 ms 46768 KB Output is correct
13 Correct 654 ms 47188 KB Output is correct
14 Correct 708 ms 47376 KB Output is correct
15 Correct 649 ms 40272 KB Output is correct
16 Correct 683 ms 42576 KB Output is correct
17 Correct 693 ms 40264 KB Output is correct
18 Runtime error 158 ms 292864 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Runtime error 132 ms 292976 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 718 ms 40104 KB Output is correct
2 Correct 1 ms 4544 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 661 ms 43864 KB Output is correct
7 Correct 661 ms 43184 KB Output is correct
8 Correct 645 ms 42996 KB Output is correct
9 Correct 678 ms 43296 KB Output is correct
10 Correct 672 ms 42840 KB Output is correct
11 Correct 647 ms 43324 KB Output is correct
12 Correct 743 ms 42680 KB Output is correct
13 Correct 687 ms 40368 KB Output is correct
14 Correct 646 ms 42308 KB Output is correct
15 Correct 707 ms 42668 KB Output is correct
16 Correct 793 ms 46784 KB Output is correct
17 Correct 743 ms 46952 KB Output is correct
18 Correct 686 ms 47448 KB Output is correct
19 Correct 662 ms 40364 KB Output is correct
20 Correct 724 ms 42420 KB Output is correct
21 Correct 697 ms 40188 KB Output is correct
22 Runtime error 148 ms 292948 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -