Submission #570505

#	Time	Username	Problem	Language	Result	Execution time	Memory
570505		grt	육각형 영역 (APIO21_hexagon)	C++17	30 / 100	39 ms	8852 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 long x, y;
};

int dx[6] = {0, 1, 1, 0, -1, -1};
int dy[6] = {2, 1, -1, -2, -1, 1};

int draw_territory(int N, int A, int B, vi dir, vi l) {
	n = N;
	ll onside = 0;
	vector<pt>pts = {{0, 0}};
	long long x = 0, y = 0;
	for(int i = 0; i < n; ++i) {
		onside += l[i];
		x += (ll)dx[dir[i]-1] * l[i];
		y += (ll)dy[dir[i]-1] * l[i];
		pts.PB({x, y});
	}
	long long p = 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;
	}
	if(p < 0) p = -p;
	ll cnt = 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: 15 / 15
• Subtask 6: 0 / 19
• Subtask 7: 0 / 18
• Subtask 8: 0 / 16