Submission #568665

#	Time	Username	Problem	Language	Result	Execution time	Memory
568665		amunduzbaev	Hexagonal Territory (APIO21_hexagon)	C++17	20 / 100	1203 ms	1048576 KiB

hexagon

#include "hexagon.h"

#ifndef EVAL
#include "grader.cpp"
#endif

#include "bits/stdc++.h"
using namespace std;
#define ar array
const int mod = 1e9 + 7;
const int N = 2e3 + 5;
int is[N][N], used[N][N];

int bp(int a, int b){
	int r = 1;
	while(b){
		if(b & 1) r = r * 1ll * a % mod;
		b >>= 1, a = a * 1ll * a % mod;
	} return r;
}

int draw_territory(int n, int A, int B, vector<int> d, vector<int> l) {
	if(n == 3){
		int L = l[0];
		int res = (L + 1) * 1ll * (L + 2) / 2 % mod * A % mod;
		res = (res + L * 1ll * (L + 1) % mod * (2 * L + 1) % mod * bp(6, mod - 2) % mod * B % mod) % mod; 
		res = (res + L * 1ll * (L + 1) / 2 % mod * B % mod) % mod;
		return res;
	}
	
	//~ assert(false);
	int ch[6][3] = {
		{1, 1},
		{1, 0},
		{0, -1},
		{-1, -1},
		{-1, 0},
		{0, 1}
	};
	
	ar<int, 2> c {}; 
	vector<ar<int, 2>> p; p.push_back(c);
	int _X = 0, _Y = 0;
	for(int i=0;i<n;i++){ --d[i];
		for(int k=0;k<l[i];k++){
			for(int t=0;t<2;t++) c[t] += ch[d[i]][t];
			p.push_back(c);
			_X = min(_X, c[0]);
			_Y = min(_Y, c[1]);
		}
	}
	
	//~ cout<<_X<<" "<<_Y<<"\n";
	_X = 1 - _X, _Y = 1 - _Y;
	//~ cout<<"\n";
	int last = 1;
	for(auto& x : p){
		x[0] = x[0] + _X; 
		x[1] = x[1] + _Y; 
		is[x[0]][x[1]] = last++;
	} 
	
	queue<int> q;
	for(int i=0;i<N;i++){
		used[0][i] = used[i][0] = used[N - 1][i] = used[i][N - 1] = 1;
		q.push(i);
		q.push(N * (N - 1) + i);
		if(i && i + 1 < N){
			q.push(i * N);
			q.push(i * N + N - 1);
		}
	}
	
	auto check = [&](int x, int y) { return (0 <= x && x < N && 0 <= y && y < N); };
	
	while(!q.empty()){
		int u = q.front(); q.pop();
		int x = u / N, y = u % N;
		for(int t=0;t<6;t++){
			//~ if(ch[t][0] == ch[t][1]) continue;
			int tx = x + ch[t][0], ty = y + ch[t][1];
			if(check(tx, ty) && !is[tx][ty] && !used[tx][ty]){
				used[tx][ty] = 1;
				q.push(tx * N + ty);
			}
		}
	}
	
	//~ for(int i=0;i<15;i++){
		//~ for(int j=0;j<15;j++){
			//~ cout<<is[i][j]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
	
	//~ _X = 1 - _X;
	//~ _Y = 1 - _Y;
	memset(is, 0, sizeof is);
	q.push(_X * N + _Y);
	is[_X][_Y] = 1;
	while(!q.empty()){
		int u = q.front(); q.pop();
		int x = u / N, y = u % N;
		for(int t=0;t<6;t++){
			//~ if(ch[t][0] == ch[t][1]) continue;
			int tx = x + ch[t][0], ty = y + ch[t][1];
			if(check(tx, ty) && !is[tx][ty] && !used[tx][ty]){
				is[tx][ty] = is[x][y] + 1;
				q.push(tx * N + ty);
			}
		}
	}
	
	//~ for(int i=0;i<15;i++){
		//~ for(int j=0;j<15;j++){
			//~ cout<<is[i][j]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
	
	int res = 0;
	//~ vector<int> D(15);
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(!is[i][j]) continue;
			is[i][j]--;
			//~ D[is[i][j]]++;
			//~ cout<<is[i][j]<<" "<<i<<" "<<j<<"\n";
			res = (res + is[i][j] * 1ll * B + A) % mod;
		}
	}
	//~ for(int i=0;i<15;i++) cout<<i<<" "<<D[i]<<"\n";
	//~ cout<<"\n";
	return res;
}

/*

17 2 3
1 1
2 2
3 2
4 1
5 1
4 1
3 1
2 2
1 3
6 2
2 3
3 1
4 6
5 3
6 3
6 2
1 1

*/

• Subtask 1: 3 / 3
• Subtask 2: 6 / 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