oj.uz

Submission #570502

# Submission time Handle Problem Language Result Execution time Memory
570502 2022-05-30T09:42:50 Z grt Hexagonal Territory (APIO21_hexagon) C++17
15 / 100
 43 ms 13056 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Incorrect 1 ms 212 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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 1104 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 3 ms 1080 KB Output is correct
7 Correct 8 ms 2092 KB Output is correct
8 Correct 1 ms 432 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 12 ms 3348 KB Output is correct
12 Correct 11 ms 3400 KB Output is correct
13 Correct 11 ms 3412 KB Output is correct
14 Correct 11 ms 3496 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 300 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 296 KB Output is correct
19 Correct 1 ms 304 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 2 ms 1104 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 1072 KB Output is correct
9 Correct 7 ms 1996 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 11 ms 3372 KB Output is correct
14 Correct 13 ms 3400 KB Output is correct
15 Correct 10 ms 3400 KB Output is correct
16 Correct 11 ms 3472 KB Output is correct
17 Correct 1 ms 316 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 17 ms 6332 KB Output is correct
21 Correct 3 ms 1068 KB Output is correct
22 Correct 1 ms 568 KB Output is correct
23 Correct 23 ms 6872 KB Output is correct
24 Correct 36 ms 12472 KB Output is correct
25 Correct 37 ms 12664 KB Output is correct
26 Correct 19 ms 6476 KB Output is correct
27 Correct 13 ms 3848 KB Output is correct
28 Correct 9 ms 3400 KB Output is correct
29 Correct 43 ms 13056 KB Output is correct
30 Incorrect 40 ms 12992 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

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

Subtask #7
0 / 18.0

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

Subtask #8
0 / 16.0

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