oj.uz

Submission #1081031

# Submission time Handle Problem Language Result Execution time Memory
1081031 2024-08-29T17:09:51 Z pawned Hexagonal Territory (APIO21_hexagon) C++17
11 / 100
 353 ms 131156 KB 
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

#include "hexagon.h"

const ll MOD = 1e9 + 7;

ll nr(ll x) {
	x %= MOD;
	x += MOD;
	x %= MOD;
	return x;
}

int dirX[6] = {0, 1, 1, 0, -1, -1};
int dirY[6] = {-1, 0, 1, 1, 0, -1};

int N;

ll A, B;

vi D, L;

const int MAX = 4010;

vector<vector<bool>> grid(MAX, vector<bool>(MAX, false));
// true if filled

int draw_territory(int N_g, int A_g, int B_g, vector<int> D_g, vector<int> L_g) {
	N = N_g; A = A_g; B = B_g;
	for (int x : D_g)
		D.pb(x - 1);
	for (int x : L_g)
		L.pb(x);
	ii curr = {2005, 2005};
	for (int i = 0; i < N; i++) {
		grid[curr.fi][curr.se] = true;
		for (int j = 0; j < L[i]; j++) {
			curr.fi += dirX[D[i]];
			curr.se += dirY[D[i]];
			grid[curr.fi][curr.se] = true;
		}
	}
/*	cout<<"grid: "<<endl;
	for (int i = 1990; i <= 2020; i++) {
		for (int j = 1990; j <= 2020; j++) {
			if (i == 2005 && j == 2005)
				cout<<"!";
			else
				cout<<grid[i][j];
		}
		cout<<endl;
	}*/
	queue<ii> q;
	vector<vector<bool>> out(MAX, vector<bool>(MAX, false));
	q.push({0, 0});
	out[0][0] = true;
	while (!q.empty()) {
		int xc = q.front().fi;
		int yc = q.front().se;
		q.pop();
		for (int i = 0; i < 6; i++) {
			int xn = xc + dirX[i];
			int yn = yc + dirY[i];
			if (xn < 0 || xn >= MAX || yn < 0 || yn >= MAX)
				continue;
			if (!out[xn][yn] && !grid[xn][yn]) {
				q.push({xn, yn});
				out[xn][yn] = true;
			}
		}
	}
/*	cout<<"out: "<<endl;
	for (int i = 1990; i <= 2020; i++) {
		for (int j = 1990; j <= 2020; j++) {
			if (i == 2005 && j == 2005)
				cout<<"!";
			else
				cout<<out[i][j];
		}
		cout<<endl;
	}*/
	// q is empty
	vector<vi> dist(MAX, vi(MAX, 1e9));
	q.push({2005, 2005});
	dist[2005][2005] = 0;
	while (!q.empty()) {
		int xc = q.front().fi;
		int yc = q.front().se;
		q.pop();
		for (int i = 0; i < 6; i++) {
			int xn = xc + dirX[i];
			int yn = yc + dirY[i];
			if (xn < 0 || xn >= MAX || yn < 0 || yn >= MAX)
				continue;
			if (!out[xn][yn] && dist[xn][yn] == 1e9) {
				q.push({xn, yn});
				dist[xn][yn] = dist[xc][yc] + 1;
			}
		}
	}
/*	cout<<"dist: "<<endl;
	for (int i = 1990; i <= 2020; i++) {
		for (int j = 1990; j <= 2020; j++) {
			if (i == 2005 && j == 2005)
				cout<<"! ";
			else if (dist[i][j] == 1e9)
				cout<<"- ";
			else
				cout<<dist[i][j]<<" ";
		}
		cout<<endl;
	}*/
	ll total = 0;
	ll cnt = 0;
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			if (dist[i][j] != 1e9) {
				total += dist[i][j];
				total = nr(total);
				cnt++;
			}
		}
	}
	ll ans = nr(cnt * A + total * B);
	return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 130896 KB Output is correct
2 Correct 336 ms 131004 KB Output is correct
3 Correct 303 ms 130896 KB Output is correct
4 Correct 309 ms 130644 KB Output is correct
5 Correct 301 ms 130768 KB Output is correct
6 Correct 310 ms 130668 KB Output is correct
7 Correct 294 ms 130788 KB Output is correct
8 Correct 304 ms 130808 KB Output is correct
9 Correct 299 ms 130896 KB Output is correct
10 Correct 305 ms 131048 KB Output is correct
11 Correct 315 ms 130896 KB Output is correct
12 Correct 306 ms 130768 KB Output is correct
13 Correct 323 ms 130908 KB Output is correct
14 Correct 297 ms 130896 KB Output is correct
15 Correct 297 ms 130900 KB Output is correct
16 Correct 299 ms 130896 KB Output is correct
17 Correct 287 ms 130764 KB Output is correct
18 Correct 306 ms 130776 KB Output is correct
19 Correct 299 ms 130752 KB Output is correct
20 Correct 311 ms 130896 KB Output is correct

Subtask #4
0 / 12.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 130756 KB Output is correct
2 Correct 319 ms 130756 KB Output is correct
3 Correct 298 ms 130812 KB Output is correct
4 Correct 302 ms 130752 KB Output is correct
5 Correct 342 ms 130896 KB Output is correct
6 Correct 312 ms 130784 KB Output is correct
7 Correct 293 ms 130900 KB Output is correct
8 Correct 319 ms 131156 KB Output is correct
9 Correct 297 ms 130900 KB Output is correct
10 Correct 299 ms 130780 KB Output is correct
11 Correct 296 ms 130748 KB Output is correct
12 Correct 310 ms 130788 KB Output is correct
13 Correct 308 ms 130800 KB Output is correct
14 Correct 308 ms 130800 KB Output is correct
15 Correct 306 ms 130860 KB Output is correct
16 Correct 293 ms 130896 KB Output is correct
17 Correct 294 ms 130896 KB Output is correct
18 Runtime error 6 ms 4952 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

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

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 130896 KB Output is correct
2 Runtime error 6 ms 4952 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -