제출 #795870

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
795870		GusterGoose27	육각형 영역 (APIO21_hexagon)	C++17	0 / 100	1 ms	468 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;

typedef pair<ll, ll> pii;

bool operator<(rad a, rad b) {
    return pii(a.a, a.b) < pii(b.a, b.b);
}

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)), };

map<prr, int> dist;

int dir(int d, bool cc) {
    return (cc) ? (d+2)%6 : (d+4)%6;
}

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)
    // 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(perim <= 2000);
    assert(sum.a == 0);
    bool cc = 1;
    if (sum.b < 0) {
        cc = 0;
        sum.b = -sum.b;
    }
    sum = sum+rad(perim, 0)*rad(0, 2);
    ll num_elems = 1+sum.b/4;
    num_elems %= MOD;
    ll ans = (A*num_elems)%MOD;
    // assert(cc);
    for (int i = 0; i < n; i++) {
        int s = dir(D[i], cc);
        for (int j = 0; j < L[i]; j++) {
            dist[cur+conv[s]] = -1;
            cur = cur+conv[D[i]];
        }
        for (int j = s; j != dir(D[(i+1)%n], cc); j = (cc ? (j+5)%6 : (j+1)%6)) {
            dist[cur+conv[j]] = -1;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < L[i]; j++) {
            dist.erase(cur);
            cur = cur+conv[D[i]];
        }
    }
    dist[cur] = 0;
    queue<prr> q;
    q.push(cur);
    while (!q.empty()) {
        prr tp = q.front();
        q.pop();
        ans += ((ll)B*dist[tp])%MOD;
        ans %= MOD;
        for (int i = 0; i < 6; i++) {
            prr nxt = tp+conv[i];
            if (dist.find(nxt) == dist.end()) {
                dist[nxt] = 1+dist[tp];
                q.push(nxt);
            }
        }
    }
    return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 15
• Subtask 6: 0 / 19
• Subtask 7: 0 / 18
• Subtask 8: 0 / 16