結果

問題 No.602 隠されていたゲーム2
コンテスト
ユーザー nanae
提出日時 2017-12-02 00:13:04
言語 D
(dmd 2.109.1)
結果
WA  
実行時間 -
コード長 3,109 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 779 ms
コンパイル使用メモリ 119,448 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-12 22:45:01
合計ジャッジ時間 1,856 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import std.stdio, std.string, std.conv, std.algorithm, std.numeric;
import std.range, std.array, std.math, std.typecons, std.container, core.bitop;

immutable long inf = 10^^9 + 7;
alias Edge = Tuple!(int, "to", long, "flow", long, "cap", int, "rev");

void main() {
    int n;
    scan(n);
    auto d = readln.split.to!(int[]);
    int x, y;
    scan(x, y);

    int L = abs(x) + abs(y);

    if (L == 0) {
        writeln(0);
        return;
    }

    d.sort();

    foreach (i ; 0 .. n) {
        if (d[i] == L) {
            writeln(1);
            return;
        }
    }

    foreach (i ; 0 .. n) {
        int r = L - d[i];
        auto ub = d.assumeSorted.lowerBound(r + 1);

        debug {
            writeln(ub);
        }

        if (!ub.empty && ub.back == r) {
            writeln(2);
            return;
        }
    }

    writeln(-1);
}

long Dinic(Edge[][] adj, int s, int t) {
    int n = adj.length.to!int;
    int[] level = new int[](n);
    int[] prog = new int[](n);
    auto q = Queue!(int)(n);

    bool bfs() {
        level[] = -1;
        level[s] = 0;
        q.clear();
        q.push(s);

        while (!q.empty) {
            auto u = q.front;
            q.pop;

            foreach (e ; adj[u]) {
                if (level[e.to] == -1 && e.cap - e.flow > 0) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }

        return level[t] != -1;
    }

    long dfs(int u, long f) {
        if (u == t) return f;

        for (; prog[u] < adj[u].length; prog[u]++) {
            auto e = &adj[u][prog[u]];

            if (level[u] + 1 == level[e.to] && e.flow < e.cap) {
                long d = dfs(e.to, min(f, e.cap - e.flow));

                if (d > 0) {
                    e.flow += d;
                    adj[e.to][e.rev].flow -= d;
                    return d;
                }
            }
        }

        return 0;
    }

    long F;

    while (bfs()) {
        prog[] = 0;

        while (true) {
            auto df = dfs(s, inf);

            if (df) F += df;
            else break;
        }
    }

    return F;
}


struct Queue(T) {
    private {
        int N, head, tail;
        T[] data;
    }

    this (int n) {
        N = n + 1;
        data = new T[](N);
    }

    bool empty() {
        return head == tail;
    }

    bool full() {
        return (tail + 1) % N == head;
    }

    T front() {
        return data[head];
    }

    void push(T x) {
        assert(!full);
        data[tail++] = x;
        tail %= N;
    }

    void pop() {
        assert(!empty);
        head++;
        head %= N;
    }

    void clear() {
        head = tail = 0;
    }
}


void scan(T...)(ref T args) {
    string[] line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}


void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}
0