Submission #569405

#	Time	Username	Problem	Language	Result	Execution time	Memory
569405		anmichi	Hexagonal Territory (APIO21_hexagon)	C++17	36 / 100	33 ms	7860 KiB

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 / 3
• Subtask 2: 6 / 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