Submission #570502

#	Time	Username	Problem	Language	Result	Execution time	Memory
570502		grt	Hexagonal Territory (APIO21_hexagon)	C++17	15 / 100	43 ms	13056 KiB

hexagon

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const int nax = 200 * 1000 + 10;
const int mod = 1e9 + 7;
int n;

struct pt {
	long double x, y;
};

long double dx[6] = {0.0, 1.5, 1.5, 0, -1.5, -1.5};
long double dy[6] = {sqrt(3), sqrt(3)/2.0, -sqrt(3)/2.0, -sqrt(3), -sqrt(3)/2.0, sqrt(3)/2.0};

int draw_territory(int N, int A, int B, vi dir, vi l) {
	n = N;
	ll onside = 0;
	vector<pt>pts = {{0.0, 0.0}};
	long double x = 0.0, y = 0.0;
	for(int i = 0; i < n; ++i) {
		onside += l[i];
		x += dx[dir[i]-1] * l[i];
		y += dy[dir[i]-1] * l[i];
		pts.PB({x, y});
	}
	long double p = 0.0;
	for(int i = 1; i < (int)pts.size(); ++i) {
		p += pts[i - 1].x * pts[i].y - pts[i - 1].y * pts[i].x;
	}
	p = abs(p);
	p *= 4.0;
	p /= 3.0;
	p /= sqrt(3);
	ll cnt = roundl(p/2);
	cnt += 2;
	ll inside = (cnt - onside) / 2;
	ll total = inside + onside;
	total %= mod;
	ll ans = (ll)A * total % mod;
	if(ans < 0) ans += mod;
	return ans;
}


//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//cout << draw_territory(17, 2, 3, {1, 2, 3, 4, 5, 4, 3, 2, 1, 6, 2, 3, 4, 5, 6, 6, 1}, {1, 2, 2, 1, 1, 1, 1, 2, 3, 2, 3, 1, 6, 3, 3, 2, 1});
	//draw_territory(3, 1, 0, {1,3,5}, {1,1,1});
//}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 11
• Subtask 4: 12 / 12
• Subtask 5: 0 / 15
• Subtask 6: 0 / 19
• Subtask 7: 0 / 18
• Subtask 8: 0 / 16