Submission #1097135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097135		gyg	Hexagonal Territory (APIO21_hexagon)	C++17	12 / 100	902 ms	1048576 KiB

hexagon

#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
#define lint long long
#define arr array 
#define vct vector
#define hmap unordered_map 
#define hset unordered_set
#define pll pair<lint, lint>
#define fir first 
#define sec second
const lint MD = 1e9 + 7, N_NDS = 1e6 + 5;

lint n, a, b;
vct<lint> drc, lng;

lint md(lint x) { return (x + MD) % MD; }

pll mv(pll pt, lint drc, lint lng) {
    pll dlt;
    if (drc == 1) dlt = {0, 1};
    if (drc == 2) dlt = {1, 1};
    if (drc == 3) dlt = {1, 0};
    if (drc == 4) dlt = {0, -1};
    if (drc == 5) dlt = {-1, -1};
    if (drc == 6) dlt = {-1, 0};
    return {pt.fir + dlt.fir * lng, pt.sec + dlt.sec * lng};
}
vct<pll> gt_pts() {
    pll pt = {0, 0};
    vct<pll> ans;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < lng[i]; j++) {
            pt = mv(pt, drc[i], 1);
            ans.push_back(pt);
        }
    }
    return ans;
}
vct<pll> nghbrs(pll pt) {
    vct<pll> ans;
    for (int i = 1; i <= 6; i++) ans.push_back(mv(pt, i, 1));
    return ans;
}
set<pll> pt_nds, pth_nds, vs;
void dfs(pll pt) {
    vs.insert(pt);
    for (pll nw_pt : nghbrs(pt))
        if (pt_nds.count(nw_pt) && !vs.count(nw_pt) && !pth_nds.count(nw_pt)) dfs(nw_pt);
}
hmap<lint, vct<pll>> clmns;
int n_nds;
arr<lint, N_NDS> x;
arr<pll, N_NDS> y;
lint prcmp() {
    vct<pll> pts = gt_pts();
    for (pll pt : pts) {
        pt_nds.insert(pt), pth_nds.insert(pt);
        for (pll nw_pt : nghbrs(pt)) pt_nds.insert(nw_pt);
    }
    
    // Node with minimum x coordinate should be on outside
    pll mn_x;
    for (pll pt : pt_nds) mn_x = min(mn_x, pt);
    dfs(mn_x);

    for (pll pt : pts) clmns[pt.fir].push_back(pt);
    for (pair<lint, vct<pll>> clmn : clmns) {
        sort(clmn.sec.begin(), clmn.sec.end());
        for (pll pt : clmn.sec) {
            if (vs.count({pt.fir, pt.sec - 1})) n_nds++, x[n_nds] = clmn.fir, y[n_nds] = {pt.sec, 0};
            if (vs.count({pt.fir, pt.sec + 1})) y[n_nds].sec = pt.sec;
        }
    }

    // for (int u = 1; u <= n_nds; u++) {
    //     cout << u << ": " << x[u] << " " << y[u].fir << " " << y[u].sec << endl;
    // }

    lint ans = 0;
    for (int u = 1; u <= n_nds; u++) ans += y[u].sec - y[u].fir + 1;
    return ans;
}

int draw_territory(int _n, int _a, int _b, vct<int> _drc, vct<int> _lng) {
    n = _n, a = _a, b = _b;
    for (int i = 0; i < n; i++) drc.push_back(_drc[i]), lng.push_back(_lng[i]);

    lint ar = prcmp();
    return md(a * ar);
}

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