Submission #1081031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081031		pawned	Hexagonal Territory (APIO21_hexagon)	C++17	11 / 100	353 ms	131156 KiB

hexagon

#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
• Subtask 2: 0 / 6
• Subtask 3: 11 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 15
• Subtask 6: 0 / 19
• Subtask 7: 0 / 18
• Subtask 8: 0 / 16