Submission #795862

#	Time	Username	Problem	Language	Result	Execution time	Memory
795862		GusterGoose27	Hexagonal Territory (APIO21_hexagon)	C++17	36 / 100	29 ms	3416 KiB

hexagon

#include "hexagon.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MOD = 1e9+7;

class rad {
public:
    ll a, b; // a + bsqrt(3)
    rad() {}
    rad(ll a, ll b) : a(a), b(b) {}
};

typedef pair<rad, rad> prr;

rad operator+(rad a, rad b) {
    return rad(a.a+b.a, a.b+b.b);
}

rad operator*(rad a, rad b) {
    return rad(a.a*b.a+3*a.b*b.b, a.a*b.b+a.b*b.a);
}

// ll operator/(rad a, rad b) {
//     assert(a.a/b.a == a.b/b.b); // probably good enough even though flooring
//     return a.a/b.a;
// }

rad operator-(rad a, rad b) {
    return rad(a.a-b.a, a.b-b.b);
}

rad operator*(prr a, prr b) { // cross product
    return a.first*b.second-a.second*b.first;
}

prr operator+(prr a, prr b) {
    return prr(a.first+b.first, a.second+b.second);
}

prr operator*(prr a, int b) {
    return prr(a.first*rad(b, 0), a.second*rad(b, 0));
}

prr conv[6] = {prr(rad(0, 0), rad(2, 0)), prr(rad(0, 1), rad(1, 0)), prr(rad(0, 1), rad(-1, 0)), 
    prr(rad(0, 0), rad(-2, 0)), prr(rad(0, -1), rad(-1, 0)), prr(rad(0, -1), rad(1, 0)), };

int draw_territory(int n, int A, int B, vector<int> D, vector<int> L) {
    // the distance between hex centers is 2 => base is 2/sqrt(3)
    // => area is 6/sqrt(3) = 2sqrt(3)
    vector<int> vals({L[0], L[0]+1, 2*L[0]+4});
    ll ans = 1;
    bool a = 0;
    bool b = 0;
    for (int v: vals) {
        int num = v;
        if (!a && num % 2 == 0) {
            num /= 2;
            a = 1;
        }
        if (!b && num % 3 == 0) {
            num /= 3;
            b = 1;
        }
        ans = (ans*num)%MOD;
    }
    // assert(B == 0);
    prr cur(rad(0, 0), rad(0, 0));
    rad sum(0, 0);
    ll perim = 0;
    for (int i = 0; i < n; i++) {
        perim += L[i];
        D[i]--;
        prr nxt = cur+conv[D[i]]*L[i];
        sum = sum+(cur*nxt);
        cur = nxt;
    }
    assert(sum.a == 0);
    if (sum.b < 0) sum.b = -sum.b;
    sum = sum+rad(perim, 0)*rad(0, 2);
    ll num_elems = 1+sum.b/4;
    num_elems %= MOD;
    return ((A*num_elems)%MOD+(B*ans)%MOD)%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