Submission #568683

#	Time	Username	Problem	Language	Result	Execution time	Memory
568683		amunduzbaev	Hexagonal Territory (APIO21_hexagon)	C++17	32 / 100	1598 ms	1048576 KiB

hexagon

#include "hexagon.h"

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

#include "bits/stdc++.h"
using namespace std;
#define ar array
using ll = long long;
const int mod = 1e9 + 7;
const int N = 2e3 + 5;
int is[N][N], used[N][N];
int ch[6][3] = {
	{1, 1},
	{1, 0},
	{0, -1},
	{-1, -1},
	{-1, 0},
	{0, 1}
};

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

namespace subtask_4{

const int N = 2e5 + 5;
vector<int> cnt[N];

int solve(int n, int A, int B, vector<int> d, vector<int> l){
	
	ar<int, 2> c {}; 
	vector<ar<int, 2>> p, tt; // 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++){
			ar<int, 2> last = c;
			for(int t=0;t<2;t++) c[t] += ch[d[i]][t];
			if(c[1] != last[1]){
				if(c[1] > last[1]) tt.push_back(c);
				else tt.push_back(last);
			} p.push_back(c);
			_X = min(_X, c[0]);
			_Y = min(_Y, c[1]);
		}
	}
	
	_X = 1 - _X, _Y = 1 - _Y;
	for(auto& x : p){
		x[0] += _X, x[1] += _Y; 
		//~ cnt[x[0] + x[1]].push_back(x[1]);
	} 
	for(auto x : tt){
		x[0] += _X, x[1] += _Y;
		cnt[x[1]].push_back(x[0]);
	}
	
	for(int i=0;i<N;i++) sort(cnt[i].begin(), cnt[i].end());
	auto check = [&](int x, int y){
		int j = lower_bound(cnt[y].begin(), cnt[y].end(), x) - cnt[y].begin();
		j = cnt[y].size() - j;
		//~ for(auto x : cnt[y]) cout<<x<<" ";
		//~ cout<<"\n";
		//~ cout<<x<<" "<<y<<" "<<j<<"\n";
		return (j & 1);
	};
	
	sort(p.begin(), p.end());
	int res = 0;
	for(int i=0, j=0;i<(int)p.size(); i = j){
		vector<int> t;
		while(j < (int)p.size() && p[i][0] == p[j][0]){
			t.push_back(p[j][1]);
			j++;
		}
		
		int m = (int)t.size(), x = p[i][0];
		res = (res + m) % mod;
		for(int k=1;k<m;k++){
			if(t[k - 1] + 1 == t[k]) continue;
			if(check(x, t[k - 1] + 1)){
				res = (res + t[k] - t[k - 1] - 1);
			}
		}
	}
	
	res = res * 1ll * A % mod;
	return res;
}

};

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;
	}
	
	ll sum = accumulate(l.begin(), l.end(), 0ll);
	if(sum > 2000){
		assert(B == 0);
		return subtask_4::solve(n, A, B, d, l);
	}
	
	//~ cout<<subtask_4::solve(n, A, B, d, l)<<"\n";
	
	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]);
		}
	}
	
	_X = 1 - _X, _Y = 1 - _Y;
	int last = 1;
	for(auto& x : p){
		x[0] = x[0] + _X; 
		x[1] = x[1] + _Y; 
		is[x[0]][x[1]] = last++;
	} 
	
	//~ for(int i=1;i<=15;i++){
		//~ for(int j=1;j<=15;j++){
			//~ cout<<is[i][j]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
	
	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++){
			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);
			}
		}
	}
	
	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++){
			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=1;i<=15;i++){
		//~ for(int j=1;j<=15;j++){
			//~ cout<<(!used[i][j])<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
	
	int res = 0; //, cc = 0;
	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;
			//~ cc = cc + A;
		}
	}
	
	//~ cout<<cc<<"\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: 12 / 12
• Subtask 5: 0 / 15
• Subtask 6: 0 / 19
• Subtask 7: 0 / 18
• Subtask 8: 0 / 16