oj.uz

Submission #980585

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

using namespace std;

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;

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

int draw_territory(int n, int A, int B,
                   vector<int> D, vector<int> L) {
    
    for (int c : L) sumL += c;
    
    if (sumL <= 2000) {
        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;
            }
        }
        // for (int i = 0; i < 2 * N; i++) {
        //     for (int j = 0; j < 2 * N; j++) {
        //         cout << grid[i][j];
        //     }
        //     cout << '\n';
        // }
        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;
    }

    return 0;
}

Compilation message

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

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 299 ms 64224 KB Output is correct
2 Correct 276 ms 64332 KB Output is correct
3 Correct 304 ms 64424 KB Output is correct
4 Correct 281 ms 64340 KB Output is correct
5 Correct 284 ms 64356 KB Output is correct
6 Correct 292 ms 64336 KB Output is correct
7 Correct 286 ms 64156 KB Output is correct
8 Correct 279 ms 64276 KB Output is correct
9 Correct 279 ms 64340 KB Output is correct
10 Correct 289 ms 64420 KB Output is correct
11 Correct 299 ms 64164 KB Output is correct
12 Correct 336 ms 64552 KB Output is correct
13 Correct 295 ms 64340 KB Output is correct
14 Correct 282 ms 64352 KB Output is correct
15 Correct 304 ms 64340 KB Output is correct
16 Correct 285 ms 64156 KB Output is correct
17 Correct 286 ms 64228 KB Output is correct
18 Correct 337 ms 64372 KB Output is correct
19 Correct 281 ms 64516 KB Output is correct
20 Correct 294 ms 64332 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 64592 KB Output is correct
2 Correct 275 ms 64284 KB Output is correct
3 Correct 283 ms 64300 KB Output is correct
4 Correct 293 ms 64340 KB Output is correct
5 Correct 279 ms 64344 KB Output is correct
6 Correct 309 ms 64272 KB Output is correct
7 Correct 280 ms 64340 KB Output is correct
8 Correct 295 ms 64368 KB Output is correct
9 Correct 287 ms 64340 KB Output is correct
10 Correct 300 ms 64340 KB Output is correct
11 Correct 280 ms 64136 KB Output is correct
12 Correct 276 ms 64140 KB Output is correct
13 Correct 302 ms 64340 KB Output is correct
14 Correct 278 ms 64228 KB Output is correct
15 Correct 289 ms 64560 KB Output is correct
16 Correct 358 ms 64336 KB Output is correct
17 Correct 287 ms 64340 KB Output is correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

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

Subtask #8
0 / 16.0

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