#1029893 (D) No.2977 Kth Xor Pair

提出ソース

結果

問題	No.2977 Kth Xor Pair
ユーザー	Daylight
提出日時	2024-12-04 09:27:32
言語	D (dmd 2.109.1)
結果	RE
実行時間	-
コード長	5,371 bytes
コンパイル時間	5,392 ms
コンパイル使用メモリ	234,136 KB
実行使用メモリ	151,016 KB
最終ジャッジ日時	2024-12-04 09:28:05
合計ジャッジ時間	31,404 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 10,496 KB
testcase_01	AC	2 ms 13,640 KB
testcase_02	AC	18 ms 10,496 KB
testcase_03	AC	18 ms 146,848 KB
testcase_04	AC	18 ms 13,632 KB
testcase_05	AC	18 ms 10,496 KB
testcase_06	AC	19 ms 10,496 KB
testcase_07	RE	-
testcase_08	TLE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	TLE	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	TLE	-
testcase_23	TLE	-
testcase_24	TLE	-
testcase_25	RE	-
testcase_26	TLE	-
testcase_27	RE	-
testcase_28	RE	-
testcase_29	RE	-
testcase_30	RE	-
testcase_31	RE	-
testcase_32	RE	-
testcase_33	RE	-
testcase_34	RE	-
testcase_35	RE	-

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

ソースコード

raw source code

import std;
class Reader {
    DList!(string) buf;

    private void readNext() {
        while (buf.empty) {
            auto inputs = stdin.readln()[0 .. $ - 1].split(" ");
            foreach (token; inputs) {
                buf.insertBack(token);
            }
        }
    }

    void read()() {

    }

    void read(T, A...)(ref T t, ref A a) {
        if (buf.empty) {
            readNext();
        }
        static if (is(T == char[])) {
            string token = buf.front();
            t = token.dup;
            buf.removeFront();
        } else static if (isArray!(T)) {
            foreach (ref v; t) {
                read(v);
            }
        } else {
            t = buf.front.to!T;
            buf.removeFront();
        }
        read(a);
    }
}

ref auto chmin(T)(ref T a, T b) {
    if (a > b) {
        a = b;
    }
    return a;
}

ref auto chmax(T)(ref T a, T b) {
    if (a < b) {
        a = b;
    }
    return a;
}

public const int INF = 1 << 30;
public const long LINF = 2e18.to!long;

class BinaryTrie(T, int MAX_LOG = 32) {
    struct Node(T) {
        int[2] next = [-1, -1];
        long common = 0;
        T lz = T.init;
    }

    private Node!T[] nodes;

    this() {
        nodes ~= Node!T();
    }

    void apply_xor(T val) {
        nodes[0].lz ^= val;
    }

    private void push(int cur, int b) {
        if ((nodes[cur].lz >> T(b)) & T(1)) {
            swap(nodes[cur].next[0], nodes[cur].next[1]);
        }
        foreach (i; 0 .. 2) {
            if (nodes[cur].next[i] != -1) {
                nodes[nodes[cur].next[i]].lz ^= nodes[cur].lz;
            }
        }
        nodes[cur].lz = 0;
    }

    void add(T val, long cnt = 1) {
        add(val, cnt, 0, MAX_LOG - 1);
    }

    private void add(T val, long cnt, int cur, int b) {
        nodes[cur].common += cnt;
        if (b < 0)
            return;
        push(cur, b);
        int nxt = (val >> T(b)) & T(1);
        if (nodes[cur].next[nxt] == -1) {
            nodes[cur].next[nxt] = nodes.length.to!int;
            nodes ~= Node!T();
        }
        add(val, cnt, nodes[cur].next[nxt], b - 1);
    }

    void erase(T val, long cnt = 1) {
        add(val, -cnt, 0, MAX_LOG - 1);
    }

    T getMin(T x = 0) {
        return getMin(x, 0, MAX_LOG - 1);
    }

    private T getMin(T x, int cur, int b) {
        if (b < 0 || cur == -1)
            return 0;
        push(cur, b);
        long nxt = (x >> T(b)) & T(1);
        int ind = nodes[cur].next[nxt];
        if (ind == -1 || nodes[ind].common == 0) {
            nxt ^= 1;
        }
        return getMin(x, nodes[cur].next[nxt], b - 1) | (T(nxt) << T(b));
    }

    T getMax(T x) {
        return getMin(~x, 0, MAX_LOG - 1);
    }

    long lowerBound(T x) {
        return lowerBound(x, 0, MAX_LOG - 1);
    }

    private long lowerBound(T val, int cur, int b) {
        if (cur == -1 || b < 0)
            return 0;
        push(cur, b);
        long nxt = (val >> T(b)) & T(1);
        long ret = lowerBound(val, nodes[cur].next[nxt], b - 1);
        if (nxt == 1 && nodes[cur].next[0] != -1) {
            ret += nodes[nodes[cur].next[0]].common;
        }
        return ret;
    }

    long upperBound(T val) {
        return lowerBound(val + 1);
    }

    T kthMin(long k) {
        return kthMin(k, 0, MAX_LOG - 1);
    }

    private T kthMin(long k, int cur, int b) {
        if (b < 0)
            return -1;
        push(cur, b);
        int lower_ind = nodes[cur].next[0];
        long lower_cnt = 0;
        if (lower_ind != -1) {
            lower_cnt = nodes[lower_ind].common;
        }
        if (k < lower_cnt) {
            return kthMin(k, nodes[cur].next[0], b - 1);
        } else {
            return kthMin(k - lower_cnt, nodes[cur].next[1], b - 1) | (T(1) << b);
        }
    }

    T kthMax(long k) {
        return kthMin(this.length - k - 1, 0, MAX_LOG - 1);
    }

    T count(T val) {
        int cur = 0;
        foreach_reverse (b; 0 .. MAX_LOG) {
            push(cur, b);
            cur = nodes[cur].next[val >> T(b) & T(1)];
            if (cur == -1)
                return 0;
        }
        return nodes[cur].common;
    }

    @property size_t length() {
        return nodes[0].common;
    }

    @property bool empty() {
        return nodes[0].common == 0;
    }

    T opIndex(size_t index) {
        return kthMin(index);
    }

    size_t opDollar() {
        return length;
    }

    bool opBinaryRight(string op)(T a) {
        static if (op == "in") {
            return this.count(a) > 0;
        } else
            static assert(false, "Operator " ~ op ~ " not implemented");
    }

    void opOpAssign(string op)(T a) {
        static if (op == "~") {
            add(a);
        } else
            static assert(false, "Operator " ~ op ~ " not implemented");
    }
}

void main() {
	Reader reader = new Reader();
	int N, K;
	reader.read(N, K);
	int[] A = new int[N];
	reader.read(A);
	auto trie = new BinaryTrie!long();
	foreach (i; 0 .. N) {
		trie ~= A[i];
	}
	long ok = 1_000_000_005;
	long ng = -1;
	bool isOk(long x) {
		long cnt = 0;
		foreach (i; 0 .. N) {
			trie.apply_xor(A[i]);
			cnt += trie.upperBound(x);
			trie.apply_xor(A[i]);
		}
		cnt -= N;
		return cnt / 2 >= K;
	}

	while (ok - ng > 1) {
		long mid = (ok + ng) / 2;
		if (isOk(mid)) {
			ok = mid;
		} else {
			ng = mid;
		}
	}
	ok.writeln;
}

yukicoder

結果

テストケース

ソースコード