oj.uz

Submission #1081249

# Submission time Handle Problem Language Result Execution time Memory
1081249 2024-08-29T20:28:03 Z pawned Hexagonal Territory (APIO21_hexagon) C++17
3 / 100
 2 ms 1116 KB 
#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 += pos[i].fi * pos[(i + 1) % N].se;
		sl2 += pos[i].se * pos[(i + 1) % N].fi;
	}
//	cout<<"sl1, sl2: "<<sl1<<" "<<sl2<<endl;
	ll total = nr(abs(sl1 - sl2) * 4);
	for (int i = 0; i < N; i++) {
		total += (L[i] - 1) * 4;
		total = nr(total);
		int toadd = 0;
		int angle1 = angle[D[i]];
		int angle2 = angle[D[(i + 1) % N]];
		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)));
}

Compilation message

hexagon.cpp: In function 'int draw_territory(int, int, int, std::vector<int>, std::vector<int>)':
hexagon.cpp:110:7: warning: unused variable 'angle1' [-Wunused-variable]
  110 |   int angle1 = angle[D[i]];
      |       ^~~~~~
hexagon.cpp:111:7: warning: unused variable 'angle2' [-Wunused-variable]
  111 |   int angle2 = angle[D[(i + 1) % N]];
      |       ^~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 2 ms 1116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 2 ms 1116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -