#411416 (C++17) No.960 マンハッタン距離3

提出ソース

結果

問題	No.960 マンハッタン距離3
ユーザー	Pachicobue
提出日時	2019-12-23 17:32:14
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,372 ms / 2,000 ms
コード長	4,004 bytes
コンパイル時間	2,322 ms
コンパイル使用メモリ	220,824 KB
実行使用メモリ	10,880 KB
最終ジャッジ日時	2024-09-17 15:56:39
合計ジャッジ時間	28,366 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	3 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	3 ms 6,940 KB
testcase_05	AC	3 ms 6,944 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	3 ms 6,944 KB
testcase_08	AC	3 ms 6,944 KB
testcase_09	AC	3 ms 6,940 KB
testcase_10	AC	3 ms 6,940 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	3 ms 6,940 KB
testcase_13	AC	3 ms 6,944 KB
testcase_14	AC	3 ms 6,940 KB
testcase_15	AC	2 ms 6,940 KB
testcase_16	AC	3 ms 6,944 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	3 ms 6,940 KB
testcase_19	AC	3 ms 6,940 KB
testcase_20	AC	3 ms 6,944 KB
testcase_21	AC	3 ms 6,940 KB
testcase_22	AC	3 ms 6,940 KB
testcase_23	AC	3 ms 6,940 KB
testcase_24	AC	3 ms 6,940 KB
testcase_25	AC	3 ms 6,944 KB
testcase_26	AC	3 ms 6,940 KB
testcase_27	AC	3 ms 6,944 KB
testcase_28	AC	3 ms 6,940 KB
testcase_29	AC	3 ms 6,944 KB
testcase_30	AC	3 ms 6,944 KB
testcase_31	AC	3 ms 6,940 KB
testcase_32	AC	3 ms 6,940 KB
testcase_33	AC	3 ms 6,944 KB
testcase_34	AC	3 ms 6,944 KB
testcase_35	AC	3 ms 6,944 KB
testcase_36	AC	3 ms 6,944 KB
testcase_37	AC	2 ms 6,940 KB
testcase_38	AC	3 ms 6,940 KB
testcase_39	AC	3 ms 6,944 KB
testcase_40	AC	3 ms 6,940 KB
testcase_41	AC	3 ms 6,940 KB
testcase_42	AC	3 ms 6,940 KB
testcase_43	AC	3 ms 6,940 KB
testcase_44	AC	3 ms 6,944 KB
testcase_45	AC	2 ms 6,944 KB
testcase_46	AC	3 ms 6,940 KB
testcase_47	AC	3 ms 6,944 KB
testcase_48	AC	3 ms 6,944 KB
testcase_49	AC	3 ms 6,944 KB
testcase_50	AC	3 ms 6,940 KB
testcase_51	AC	3 ms 6,944 KB
testcase_52	AC	3 ms 6,944 KB
testcase_53	AC	3 ms 6,940 KB
testcase_54	AC	3 ms 6,940 KB
testcase_55	AC	3 ms 6,940 KB
testcase_56	AC	3 ms 6,940 KB
testcase_57	AC	3 ms 6,944 KB
testcase_58	AC	2 ms 6,940 KB
testcase_59	AC	3 ms 6,940 KB
testcase_60	AC	3 ms 6,940 KB
testcase_61	AC	3 ms 6,944 KB
testcase_62	AC	3 ms 6,940 KB
testcase_63	AC	3 ms 6,944 KB
testcase_64	AC	3 ms 6,944 KB
testcase_65	AC	3 ms 6,944 KB
testcase_66	AC	3 ms 6,940 KB
testcase_67	AC	3 ms 6,940 KB
testcase_68	AC	3 ms 6,940 KB
testcase_69	AC	3 ms 6,944 KB
testcase_70	AC	3 ms 6,944 KB
testcase_71	AC	3 ms 6,944 KB
testcase_72	AC	3 ms 6,940 KB
testcase_73	AC	3 ms 6,940 KB
testcase_74	AC	3 ms 6,940 KB
testcase_75	AC	3 ms 6,940 KB
testcase_76	AC	3 ms 6,940 KB
testcase_77	AC	3 ms 6,944 KB
testcase_78	AC	3 ms 6,944 KB
testcase_79	AC	3 ms 6,940 KB
testcase_80	AC	3 ms 6,940 KB
testcase_81	AC	3 ms 6,948 KB
testcase_82	AC	3 ms 6,944 KB
testcase_83	AC	3 ms 6,940 KB
testcase_84	AC	3 ms 6,944 KB
testcase_85	AC	2 ms 6,940 KB
testcase_86	AC	3 ms 6,940 KB
testcase_87	AC	3 ms 6,940 KB
testcase_88	AC	2 ms 6,944 KB
testcase_89	AC	3 ms 6,944 KB
testcase_90	AC	3 ms 6,940 KB
testcase_91	AC	3 ms 6,944 KB
testcase_92	AC	3 ms 6,944 KB
testcase_93	AC	3 ms 6,940 KB
testcase_94	AC	3 ms 6,940 KB
testcase_95	AC	3 ms 6,944 KB
testcase_96	AC	3 ms 6,944 KB
testcase_97	AC	3 ms 6,944 KB
testcase_98	AC	3 ms 6,940 KB
testcase_99	AC	3 ms 6,940 KB
testcase_100	AC	3 ms 6,944 KB
testcase_101	AC	3 ms 6,944 KB
testcase_102	AC	3 ms 6,944 KB
testcase_103	AC	2 ms 6,944 KB
testcase_104	AC	2 ms 6,940 KB
testcase_105	AC	3 ms 6,948 KB
testcase_106	AC	3 ms 6,940 KB
testcase_107	AC	3 ms 6,944 KB
testcase_108	AC	2 ms 6,940 KB
testcase_109	AC	2 ms 6,944 KB
testcase_110	AC	2 ms 6,944 KB
testcase_111	AC	3 ms 6,940 KB
testcase_112	AC	2 ms 6,944 KB
testcase_113	AC	1 ms 6,944 KB
testcase_114	AC	2 ms 6,944 KB
testcase_115	AC	2 ms 6,940 KB
testcase_116	AC	2 ms 6,944 KB
testcase_117	AC	2 ms 6,940 KB
testcase_118	AC	2 ms 6,940 KB
testcase_119	AC	2 ms 6,940 KB
testcase_120	AC	2 ms 6,944 KB
testcase_121	AC	2 ms 6,940 KB
testcase_122	AC	2 ms 6,944 KB
testcase_123	AC	2 ms 6,944 KB
testcase_124	AC	2 ms 6,940 KB
testcase_125	AC	2 ms 6,944 KB
testcase_126	AC	2 ms 6,944 KB
testcase_127	AC	2 ms 6,940 KB
testcase_128	AC	23 ms 6,940 KB
testcase_129	AC	59 ms 6,940 KB
testcase_130	AC	44 ms 6,940 KB
testcase_131	AC	73 ms 6,944 KB
testcase_132	AC	743 ms 10,112 KB
testcase_133	AC	7 ms 6,944 KB
testcase_134	AC	20 ms 6,944 KB
testcase_135	AC	136 ms 6,940 KB
testcase_136	AC	150 ms 6,944 KB
testcase_137	AC	39 ms 6,940 KB
testcase_138	AC	348 ms 8,064 KB
testcase_139	AC	449 ms 8,960 KB
testcase_140	AC	78 ms 6,940 KB
testcase_141	AC	807 ms 10,496 KB
testcase_142	AC	224 ms 6,944 KB
testcase_143	AC	50 ms 6,940 KB
testcase_144	AC	1,010 ms 9,600 KB
testcase_145	AC	63 ms 6,940 KB
testcase_146	AC	131 ms 6,944 KB
testcase_147	AC	645 ms 7,936 KB
testcase_148	AC	47 ms 6,940 KB
testcase_149	AC	75 ms 6,940 KB
testcase_150	AC	115 ms 8,192 KB
testcase_151	AC	6 ms 6,940 KB
testcase_152	AC	54 ms 6,940 KB
testcase_153	AC	82 ms 6,940 KB
testcase_154	AC	16 ms 6,940 KB
testcase_155	AC	574 ms 7,552 KB
testcase_156	AC	224 ms 6,940 KB
testcase_157	AC	649 ms 7,808 KB
testcase_158	AC	499 ms 10,624 KB
testcase_159	AC	66 ms 6,940 KB
testcase_160	AC	21 ms 6,944 KB
testcase_161	AC	895 ms 8,320 KB
testcase_162	AC	70 ms 6,944 KB
testcase_163	AC	40 ms 6,940 KB
testcase_164	AC	117 ms 8,576 KB
testcase_165	AC	78 ms 6,944 KB
testcase_166	AC	14 ms 6,940 KB
testcase_167	AC	57 ms 6,940 KB
testcase_168	AC	226 ms 6,944 KB
testcase_169	AC	304 ms 6,944 KB
testcase_170	AC	259 ms 6,940 KB
testcase_171	AC	419 ms 6,940 KB
testcase_172	AC	35 ms 6,948 KB
testcase_173	AC	9 ms 6,940 KB
testcase_174	AC	130 ms 9,600 KB
testcase_175	AC	165 ms 10,752 KB
testcase_176	AC	89 ms 7,040 KB
testcase_177	AC	13 ms 6,940 KB
testcase_178	AC	109 ms 7,296 KB
testcase_179	AC	114 ms 9,088 KB
testcase_180	AC	71 ms 6,940 KB
testcase_181	AC	16 ms 6,940 KB
testcase_182	AC	32 ms 6,940 KB
testcase_183	AC	43 ms 6,940 KB
testcase_184	AC	34 ms 6,940 KB
testcase_185	AC	53 ms 6,944 KB
testcase_186	AC	64 ms 6,940 KB
testcase_187	AC	49 ms 6,940 KB
testcase_188	AC	2 ms 6,940 KB
testcase_189	AC	2 ms 6,940 KB
testcase_190	AC	2 ms 6,940 KB
testcase_191	AC	2 ms 6,940 KB
testcase_192	AC	2 ms 6,940 KB
testcase_193	AC	2 ms 6,940 KB
testcase_194	AC	2 ms 6,944 KB
testcase_195	AC	2 ms 6,940 KB
testcase_196	AC	515 ms 7,936 KB
testcase_197	AC	110 ms 6,940 KB
testcase_198	AC	406 ms 6,944 KB
testcase_199	AC	1,372 ms 8,320 KB
testcase_200	AC	65 ms 6,940 KB
testcase_201	AC	38 ms 6,940 KB
testcase_202	AC	250 ms 7,808 KB
testcase_203	AC	327 ms 6,944 KB
testcase_204	AC	933 ms 10,624 KB
testcase_205	AC	239 ms 6,940 KB
testcase_206	AC	95 ms 6,940 KB
testcase_207	AC	54 ms 6,940 KB
testcase_208	AC	658 ms 8,576 KB
testcase_209	AC	219 ms 6,944 KB
testcase_210	AC	49 ms 6,944 KB
testcase_211	AC	222 ms 6,940 KB
testcase_212	AC	18 ms 6,944 KB
testcase_213	AC	39 ms 6,940 KB
testcase_214	AC	624 ms 10,880 KB
testcase_215	AC	951 ms 9,472 KB
testcase_216	AC	1,077 ms 10,368 KB
testcase_217	AC	446 ms 7,168 KB
testcase_218	AC	76 ms 6,940 KB
testcase_219	AC	40 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using ll = long long;
int main()
{
    using pll = std::pair<ll, ll>;
    ll W, H;
    std::cin >> W >> H;
    auto enc   = [&](ll x, ll y) -> pll { return pll{x + y, y - x}; };
    auto dec   = [&](ll x, ll y) -> pll { return std::abs(x + y) % 2 == 1 ? pll{-1, -1} : pll{(x - y) / 2, (x + y) / 2}; };
    auto L1    = [&](ll x1, ll y1, ll x2, ll y2) { return std::abs(x1 - x2) + std::abs(y1 - y2); };
    auto is_in = [&](ll x, ll y) { return 1 <= y and y <= H and 1 <= x and x <= W; };
    int N;
    std::cin >> N;
    std::vector<ll> rxs(N), rys(N);
    for (int i = 0; i < N; i++) { std::cin >> rxs[i] >> rys[i]; }
    {
        std::set<ll> parity;
        for (int i = 0; i < N; i++) { parity.insert(std::abs(rxs[i] + rys[i]) % 2); }
        if (parity.size() == 2) { return std::cout << 0 << std::endl, 0; }
    }
    std::vector<ll> xs(N), ys(N);
    for (int i = 0; i < N; i++) { std::tie(xs[i], ys[i]) = enc(rxs[i], rys[i]); }
    auto is_ok = [&](ll x, ll y) {
        if (not is_in(x, y)) { return false; }
        std::set<ll> ds;
        for (int i = 0; i < N; i++) { ds.insert(L1(rxs[i], rys[i], x, y)); }
        return ds.size() == 1;
    };
    const ll ym = *std::min_element(ys.begin(), ys.end());
    const ll xm = *std::min_element(xs.begin(), xs.end());
    const ll yM = *std::max_element(ys.begin(), ys.end());
    const ll xM = *std::max_element(xs.begin(), xs.end());
    ll ps[]     = {xm + (yM - ym) / 2, xM - (yM - ym) / 2, (xm + xM) / 2, (xm + xM) / 2};
    ll qs[]     = {(ym + yM) / 2, (ym + yM) / 2, yM - (xM - xm) / 2, ym + (xM - xm) / 2};
    for (int i = 0; i < 4; i++) { std::tie(ps[i], qs[i]) = dec(ps[i], qs[i]); }
    if (xm == xM) {
        if (not is_ok(ps[0], qs[0]) or not is_ok(ps[1], qs[1])) { return std::cout << 0 << std::endl, 0; }
        ll ans = (W - ps[0] + 1) * (H - qs[0] + 1) + ps[1] * qs[1];
        if (N == 2) { ans += (ps[0] - ps[1] - 1); }
        return std::cout << ans << std::endl, 0;
    }
    if (ym == yM) {
        if (not is_ok(ps[2], qs[2]) or not is_ok(ps[3], qs[3])) { return std::cout << 0 << std::endl, 0; }
        ll ans = (W - ps[2] + 1) * qs[2] + ps[3] * (H - qs[3] + 1);
        if (N == 2) { ans += (ps[2] - ps[3] - 1); }
        return std::cout << ans << std::endl, 0;
    }
    std::set<pll> start;
    for (int i = 0; i < 4; i++) {
        if (is_ok(ps[i], qs[i])) { start.insert({ps[i], qs[i]}); }
    }
    ll ans = start.size();
    if (start.size() == 1) {
        const auto [p, q] = *start.begin();
        constexpr ll dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
        constexpr ll dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
        for (int i = 0; i < 8; i++) {
            ll inf = 0, sup = H + W;
            while (sup - inf > 1) {
                const ll mid = (inf + sup) / 2;
                const ll np = p + mid * dx[i], nq = q + mid * dy[i];
                (is_ok(np, nq) ? inf : sup) = mid;
            }
            ans += inf;
        }
    } else if (start.size() == 2) {
        const auto [p0, q0] = *start.begin();
        const auto [p1, q1] = *start.rbegin();
        constexpr ll dx[]   = {-1, -1, -1, 0, 0, 1, 1, 1};
        constexpr ll dy[]   = {-1, 0, 1, -1, 1, -1, 0, 1};
        for (int i = 0; i < 8; i++) {
            ll inf = 0, sup = H + W;
            while (sup - inf > 1) {
                const ll mid = (inf + sup) / 2;
                const ll np = p0 + mid * dx[i], nq = q0 + mid * dy[i];
                (is_ok(np, nq) and (np != p1 or nq != q1) ? inf : sup) = mid;
            }
            ans += inf;
        }
        for (int i = 0; i < 8; i++) {
            if (dx[i] != 0 and dy[i] != 0) { continue; }
            ll inf = 0, sup = H + W;
            while (sup - inf > 1) {
                const ll mid = (inf + sup) / 2;
                const ll np = p1 + mid * dx[i], nq = q1 + mid * dy[i];
                (is_ok(np, nq) ? inf : sup) = mid;
            }
            ans += inf;
        }
    }
    std::cout << ans << std::endl;
    return 0;
}

yukicoder

結果

テストケース

ソースコード