Submission #1081253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081253		pawned	Hexagonal Territory (APIO21_hexagon)	C++17	3 / 100	3 ms	860 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;
}

ll binpow(ll x, ll y) {
	x = nr(x);
	ll res = 1;
	while (y > 0) {
		if (y % 2 == 1)
			res = nr(res * x);
		x = nr(x * x);
		y /= 2;
	}
	return res;
}

ll inv(ll x) {
	return binpow(x, MOD - 2);
}

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

int angle[6] = {0, 2, 3, 4, 6, 7};

vector<vi> turn = {		{4, 2, 1, 0, 6, 5},
						{6, 4, 3, 2, 0, 7},
						{7, 5, 4, 3, 1, 0},
						{0, 6, 5, 4, 2, 1},
						{2, 0, 7, 6, 4, 3},
						{3, 1, 0, 7, 5, 4}};
// counterclockwise turns

void precomp() {

}

int N;

ll A, B;

vi D, L;

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);
	vector<ii> pos;
	pos.pb({0, 0});
	for (int i = 0; i < N; i++) {
		ll cx = pos.back().fi;
		ll cy = pos.back().se;
		cx += dirX[D[i]] * L[i];
		cy += dirY[D[i]] * L[i];
		pos.pb({cx, cy});
	}
/*	cout<<"pos: ";
	for (ii p : pos)
		cout<<"("<<p.fi<<", "<<p.se<<"); ";
	cout<<endl;*/
	int sum1 = 0;	// counterclockwise sum
	int sum2 = 0;	// clockwise sum
	for (int i = 0; i < N; i++) {
		int diff = angle[D[(i + 1) % N]] - angle[D[i]];
		if (diff != 0) {
			if (diff < 0) {	// counterclockwise turn
				sum1 += -diff;
				sum2 += (8 + diff);
			}
			else {	// clockwise turn
				sum1 += (8 - diff);
				sum2 += diff;
			}
		}
	}
//	cout<<"sum1, sum2: "<<sum1<<" "<<sum2<<endl;
	ll sl1 = 0;	// shoelace, i <=> i+1
	ll sl2 = 0;	// shoelace, i+1 <=> i
	for (int i = 0; i < N; i++) {
		sl1 += nr(nr(pos[i].fi) * nr(pos[(i + 1) % N].se));
		sl1 = nr(sl1);
		sl2 += nr(nr(pos[i].se) * nr(pos[(i + 1) % N].fi));
		sl2 = nr(sl2);
	}
	// need to know the direction
//	cout<<"sl1, sl2: "<<sl1<<" "<<sl2<<endl;
	ll total = nr((sl2 - sl1) * 4);
	if (sum1 > sum2) {
		total = nr(-total);
	}
	for (int i = 0; i < N; i++) {
		total += (L[i] - 1) * 4;
		total = nr(total);
		int toadd = 0;
		if (sum1 < sum2)	// counterclockwise
			toadd = turn[D[i]][D[(i + 1) % N]];
		else	// clockwise
			toadd = 8 - turn[D[i]][D[(i + 1) % N]];
		total += toadd;
		total = nr(total);
	}
//	cout<<"total: "<<total<<endl;
	return nr(A * nr(total * inv(8)));
}

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