oj.uz

Submission #980603

# Submission time Handle Problem Language Result Execution time Memory
980603 2024-05-12T09:17:40 Z vjudge1 Hexagonal Territory (APIO21_hexagon) C++17
11 / 100
 334 ms 64536 KB 
#include <bits/stdc++.h>
#include "hexagon.h"

using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;

void norm(int &x) {
    if (x >= MOD) x -= MOD;
    if (x < 0) x += MOD;
}

struct point {
    int x;
    int y;
    point() {}
    point(int x, int y) : x(x), y(y) {} 
};
pair<int, int> directions[6] = {
    {-1, -1}, {-1, 0}, {0, +1}, {+1, +1}, {+1, 0}, {0, -1}
};

point move(point a, int dir) {
    return point(a.x + directions[dir].first, 
                a.y + directions[dir].second);
}

int sumL = 0;

namespace Third {
const int N = 2020;
int grid[2 * N][2 * N] = {};

point start = {N, N};
int cnt = 0;
int sumD = 0;
bool inside(point a) {
    return (a.x >= 0 && a.x < 2 * N && a.y >= 0 && a.y < 2 * N);
}

void coloring(point a, int color) {
    grid[a.x][a.y] = color;
    queue<point> q;
    q.push(a);
    while (!q.empty()) {
        point v = q.front();
        q.pop();
        for (int i = 0; i < 6; i++) {
            point to = move(v, i);
            if (inside(to) && !grid[to.x][to.y]) {
                grid[to.x][to.y] = color;
                q.push(to);
            }

        }
    }
}
void bfs() {
    queue<pair<point, int>> q;
    q.push({start, 0});
    grid[start.x][start.y] = 3;

    while (!q.empty()) {
        point v = q.front().first;
        int d = q.front().second;
        q.pop();
        cnt++;
        sumD += d; norm(sumD);  
        for (int i = 0; i < 6; i++) {
            point to = move(v, i);
            if (!inside(to)) continue;
            if (grid[to.x][to.y] == 1 || grid[to.x][to.y] == 2) {
                grid[to.x][to.y] = 3;
                q.push({to, d + 1});
            }
        }
    }
}
};

namespace Fourth {
    map<int, vector<int>> MP;
}
int draw_territory(int n, int A, int B,
                   vector<int> D, vector<int> L) {
    
    for (int c : L) sumL += c;
    
    if (sumL <= 2000) {
        using namespace Third;
        point cur = start;

        grid[cur.x][cur.y] = 2;
        int kk = 0;
        for (int i = 0; i < n; i++) {
            D[i]--;
            while (L[i]--) {
                cur = move(cur, D[i]);
                grid[cur.x][cur.y] = 2;
            }
        }
        coloring(point(0, 0), 4);
        point p(0, 0);

        for (int i = 0; i < 2 * N; i++) {
            for (int j = 0; j < 2 * N; j++) {
                if (!grid[i][j]) {
                    coloring(point(i, j), 1);
                }
            }
        }

        bfs();
        return (1ll * cnt * A % MOD + 1ll * sumD * B % MOD) % MOD;
    }

    if (n == 3) {
        int ln = L[0] + 1;
        ll c = ln * (ln + 1) / 2;
        ll d = ln * (ln + 1) * (2 * ln + 1) / 6 - (ln) * (ln + 1) / 2;
        c %= MOD, d %= MOD;
        return (c * A + d * B) % MOD;
    }
    return 0;
}

Compilation message

hexagon.cpp: In function 'int draw_territory(int, int, int, std::vector<int>, std::vector<int>)':
hexagon.cpp:95:13: warning: unused variable 'kk' [-Wunused-variable]
   95 |         int kk = 0;
      |             ^~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 64236 KB Output is correct
2 Correct 323 ms 64232 KB Output is correct
3 Correct 295 ms 64184 KB Output is correct
4 Correct 296 ms 64364 KB Output is correct
5 Correct 303 ms 64160 KB Output is correct
6 Correct 298 ms 64244 KB Output is correct
7 Correct 279 ms 64336 KB Output is correct
8 Correct 285 ms 64472 KB Output is correct
9 Correct 278 ms 64336 KB Output is correct
10 Correct 319 ms 64164 KB Output is correct
11 Correct 284 ms 64340 KB Output is correct
12 Correct 298 ms 64260 KB Output is correct
13 Correct 292 ms 64268 KB Output is correct
14 Correct 279 ms 64340 KB Output is correct
15 Correct 293 ms 64288 KB Output is correct
16 Correct 277 ms 64468 KB Output is correct
17 Correct 324 ms 64116 KB Output is correct
18 Correct 292 ms 64292 KB Output is correct
19 Correct 287 ms 64444 KB Output is correct
20 Correct 302 ms 64340 KB Output is correct

Subtask #4
0 / 12.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 64520 KB Output is correct
2 Correct 282 ms 64336 KB Output is correct
3 Correct 279 ms 64284 KB Output is correct
4 Correct 296 ms 64336 KB Output is correct
5 Correct 280 ms 64340 KB Output is correct
6 Correct 283 ms 64368 KB Output is correct
7 Correct 294 ms 64280 KB Output is correct
8 Correct 290 ms 64536 KB Output is correct
9 Correct 280 ms 64340 KB Output is correct
10 Correct 313 ms 64356 KB Output is correct
11 Correct 298 ms 64160 KB Output is correct
12 Correct 302 ms 64220 KB Output is correct
13 Correct 334 ms 64208 KB Output is correct
14 Correct 281 ms 64220 KB Output is correct
15 Correct 281 ms 64180 KB Output is correct
16 Correct 310 ms 64220 KB Output is correct
17 Correct 307 ms 64300 KB Output is correct
18 Incorrect 1 ms 344 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

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

Subtask #8
0 / 16.0

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