Submission #980433

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
980433	2024-05-12T07:20:09 Z	vjudge1	Hexagonal Territory (APIO21_hexagon)	C++17	21 / 100	2000 ms	369392 KB

hexagon

#include "hexagon.h"

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;

long long pw(long long x, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) {
            res = res * x % mod;
        }
        n /= 2;
        x = x * x % mod;
    }
    return res;
}

int dx[6] = {-1, -1, 0, 1, 1, 0};
int dy[6] = {-1, 0, 1, 1, 0, -1};

int draw_territory(int N, int A, int B,
                   std::vector<int> D, std::vector<int> L) {

    long long X = 0, Y = 0;

    if (N == 3) {
        assert (L[0] == L[1]);
        assert (L[1] == L[2]);

        long long x = L[0] + 1;
        X = x * (x + 1) / 2;
        Y = x * (x + 1) % mod * (2 * x + 1) % mod * pw(6, mod - 2) - X;
    } else {
        vector<pair<int, int>> p;
        set<pair<int, int>> fucked;

        int x = 0, y = 0;
        for (int i = 0; i < N; i++) {
            int dir = D[i] - 1;
            for (int j = 0; j < L[i]; j++) {
                x += dx[dir];
                y += dy[dir];
                p.push_back({x, y});

                for (int h = 0; h < 6; h++) {
                    fucked.insert({x + dx[h], y + dy[h]});
                }
            }
        }
        for (auto xi: p) {
            fucked.erase(xi);
        }

        set<pair<int, int>> outers;
        queue<pair<int, int>> q;

        q.push(*fucked.begin());
        outers.insert(*fucked.begin());

        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int i = 0; i < 6; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (fucked.find({nx, ny}) == fucked.end()) {
                    continue;
                } else if (outers.find({nx, ny}) == outers.end()) {
                    outers.insert({nx, ny});
                    q.push({nx, ny});
                }
            }
        }

        for (auto xi: p) {
            int x = xi.first;
            int y = xi.second;
            if (outers.find({x, y - 1}) != outers.end()) {
                X -= y - 1;
            }
            if (outers.find({x, y + 1}) != outers.end()) {
                X += y;
            }
        }
    }

    X %= mod;
    Y %= mod;

    long long res = X * A % mod + Y * B % mod;

    res = (res % mod + mod) % mod;

    return res;
}

Subtask #1
3.0 / 3.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct

Subtask #2
6.0 / 6.0

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

Subtask #3
0 / 11.0

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

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	337 ms	28616 KB	Output is correct
2	Correct	199 ms	17864 KB	Output is correct
3	Correct	268 ms	23236 KB	Output is correct
4	Correct	189 ms	18120 KB	Output is correct
5	Correct	269 ms	25100 KB	Output is correct
6	Correct	346 ms	29780 KB	Output is correct
7	Correct	128 ms	11204 KB	Output is correct
8	Correct	252 ms	16584 KB	Output is correct
9	Correct	347 ms	25532 KB	Output is correct
10	Correct	357 ms	28348 KB	Output is correct
11	Correct	234 ms	23744 KB	Output is correct
12	Correct	255 ms	23492 KB	Output is correct
13	Correct	276 ms	23928 KB	Output is correct
14	Correct	213 ms	18828 KB	Output is correct
15	Correct	298 ms	16056 KB	Output is correct
16	Correct	267 ms	16060 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct

Subtask #5
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	360 ms	28492 KB	Output is correct
4	Correct	198 ms	17756 KB	Output is correct
5	Correct	264 ms	23252 KB	Output is correct
6	Correct	188 ms	18120 KB	Output is correct
7	Correct	271 ms	25020 KB	Output is correct
8	Correct	337 ms	29680 KB	Output is correct
9	Correct	128 ms	11208 KB	Output is correct
10	Correct	268 ms	16580 KB	Output is correct
11	Correct	333 ms	25704 KB	Output is correct
12	Correct	361 ms	28332 KB	Output is correct
13	Correct	258 ms	23808 KB	Output is correct
14	Correct	284 ms	23488 KB	Output is correct
15	Correct	262 ms	24000 KB	Output is correct
16	Correct	209 ms	18884 KB	Output is correct
17	Correct	302 ms	16000 KB	Output is correct
18	Correct	266 ms	16012 KB	Output is correct
19	Execution timed out	2062 ms	369392 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #6
0 / 19.0

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

Subtask #7
0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Execution timed out	2100 ms	330264 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

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

Submission #980433

Compilation message