Submission #569405

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
569405	2022-05-27T11:24:23 Z	anmichi	Hexagonal Territory (APIO21_hexagon)	C++17	36 / 100	33 ms	7860 KB

hexagon

#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
template <class T, class U>
inline bool chmax(T& a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T, class U>
inline bool chmin(T& a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
constexpr int INF = 1000000000;
constexpr ll llINF = 3000000000000000000;
constexpr int mod = 1000000007;
const ll half = (mod + 1) / 2;
constexpr double eps = 1e-10;
ll modinv(ll a, ll m = mod) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
constexpr int dx[] = {1, 1, 0, -1, -1, 0}, dy[] = {1, 0, -1, -1, 0, 1};
ll cross(ll a, ll b, ll c, ll d) { return a * d - b * c; }
int draw_territory(int n, int a, int b, vector<int> d, vector<int> l) {
    if (n == 3) {
        ll s = l[0];
        ll resa = (s + 1) * (s + 2) / 2 % mod * a % mod;
        ll resb = s * (s + 1) % mod * (s + 2) % mod * modinv(3) % mod * b % mod;
        return (resa + resb) % mod;
    }
    vector<ll> x(n + 1), y(n + 1);
    rep(i, n) {
        d[i]--;
        x[i + 1] = x[i] + dx[d[i]] * l[i];
        y[i + 1] = y[i] + dy[d[i]] * l[i];
    }
    ll S = 0;
    rep(i, n) S += cross(x[i], y[i], x[i + 1], y[i + 1]);
    S = abs(S);
    rep(i, n) S += l[i];
    S /= 2;
    return (S + 1) % mod * a % mod;
}

Subtask #1
3.0 / 3.0

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

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct

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	0 ms	212 KB	Output is correct
2	Correct	2 ms	532 KB	Output is correct
3	Correct	1 ms	312 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	2 ms	568 KB	Output is correct
7	Correct	10 ms	1336 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	8 ms	1976 KB	Output is correct
12	Correct	8 ms	2004 KB	Output is correct
13	Correct	8 ms	1936 KB	Output is correct
14	Correct	9 ms	2108 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	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct

Subtask #5
15.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	0 ms	212 KB	Output is correct
4	Correct	2 ms	528 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	300 KB	Output is correct
7	Correct	2 ms	436 KB	Output is correct
8	Correct	2 ms	596 KB	Output is correct
9	Correct	8 ms	1364 KB	Output is correct
10	Correct	1 ms	308 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	8 ms	1904 KB	Output is correct
14	Correct	10 ms	2004 KB	Output is correct
15	Correct	8 ms	1876 KB	Output is correct
16	Correct	10 ms	2104 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	300 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	14 ms	3304 KB	Output is correct
21	Correct	2 ms	564 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	20 ms	4436 KB	Output is correct
24	Correct	27 ms	6732 KB	Output is correct
25	Correct	30 ms	7200 KB	Output is correct
26	Correct	15 ms	3716 KB	Output is correct
27	Correct	11 ms	2772 KB	Output is correct
28	Correct	12 ms	1908 KB	Output is correct
29	Correct	33 ms	7860 KB	Output is correct
30	Correct	32 ms	7732 KB	Output is correct
31	Correct	32 ms	7756 KB	Output is correct
32	Correct	33 ms	7492 KB	Output is correct
33	Correct	16 ms	3688 KB	Output is correct
34	Correct	8 ms	2004 KB	Output is correct
35	Correct	1 ms	212 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	1 ms	212 KB	Output is correct

Subtask #6
0 / 19.0

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

Subtask #8
0 / 16.0

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

Submission #569405

Compilation message