#482252 (C++17) No.1056 2D Lamps

提出ソース
結果

問題	No.1056 2D Lamps
ユーザー	yosupot
提出日時	2020-05-15 22:41:05
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	248 ms / 3,000 ms
コード長	22,508 bytes
コンパイル時間	1,834 ms
コンパイル使用メモリ	150,760 KB
実行使用メモリ	15,232 KB
最終ジャッジ日時	2024-09-19 11:50:11
合計ジャッジ時間	5,626 ms
ジャッジサーバーID （参考情報）	judge5 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	1 ms 6,944 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	248 ms 15,232 KB
testcase_04	AC	242 ms 15,232 KB
testcase_05	AC	247 ms 15,232 KB
testcase_06	AC	241 ms 15,104 KB
testcase_07	AC	248 ms 15,232 KB
testcase_08	AC	240 ms 15,232 KB
testcase_09	AC	117 ms 15,104 KB
testcase_10	AC	217 ms 15,232 KB
testcase_11	AC	243 ms 15,232 KB
testcase_12	AC	247 ms 15,232 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	2 ms 6,940 KB
testcase_16	AC	2 ms 6,944 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
//#undef LOCAL




#include <algorithm>

#include <array>

#include <bitset>

#include <cassert>

#include <complex>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <map>

#include <numeric>

#include <queue>

#include <set>

#include <string>

#include <unordered_map>

#include <unordered_set>

#include <vector>

using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

struct Scanner {
    FILE* fp = nullptr;
    char line[(1 << 15) + 1];
    size_t st = 0, ed = 0;
    void reread() {
        memmove(line, line + st, ed - st);
        ed -= st;
        st = 0;
        ed += fread(line + ed, 1, (1 << 15) - ed, fp);
        line[ed] = '\0';
    }
    bool succ() {
        while (true) {
            if (st == ed) {
                reread();
                if (st == ed) return false;
            }
            while (st != ed && isspace(line[st])) st++;
            if (st != ed) break;
        }
        if (ed - st <= 50) reread();
        return true;
    }
    template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
    bool read_single(T& ref) {
        if (!succ()) return false;
        while (true) {
            size_t sz = 0;
            while (st + sz < ed && !isspace(line[st + sz])) sz++;
            ref.append(line + st, sz);
            st += sz;
            if (!sz || st != ed) break;
            reread();
        }
        return true;
    }
    template <class T, enable_if_t<is_integral<T>::value, int> = 0>
    bool read_single(T& ref) {
        if (!succ()) return false;
        bool neg = false;
        if (line[st] == '-') {
            neg = true;
            st++;
        }
        ref = T(0);
        while (isdigit(line[st])) {
            ref = 10 * ref + (line[st++] - '0');
        }
        if (neg) ref = -ref;
        return true;
    }
    template <class T> bool read_single(V<T>& ref) {
        for (auto& d : ref) {
            if (!read_single(d)) return false;
        }
        return true;
    }
    void read() {}
    template <class H, class... T> void read(H& h, T&... t) {
        bool f = read_single(h);
        assert(f);
        read(t...);
    }
    Scanner(FILE* _fp) : fp(_fp) {}
};

struct Printer {
  public:
    template <bool F = false> void write() {}
    template <bool F = false, class H, class... T>
    void write(const H& h, const T&... t) {
        if (F) write_single(' ');
        write_single(h);
        write<true>(t...);
    }
    template <class... T> void writeln(const T&... t) {
        write(t...);
        write_single('\n');
    }

    Printer(FILE* _fp) : fp(_fp) {}
    ~Printer() { flush(); }

  private:
    static constexpr size_t SIZE = 1 << 15;
    FILE* fp;
    char line[SIZE], small[50];
    size_t pos = 0;
    void flush() {
        fwrite(line, 1, pos, fp);
        pos = 0;
    }
    void write_single(const char& val) {
        if (pos == SIZE) flush();
        line[pos++] = val;
    }
    template <class T, enable_if_t<is_integral<T>::value, int> = 0>
    void write_single(T val) {
        if (pos > (1 << 15) - 50) flush();
        if (val == 0) {
            write_single('0');
            return;
        }
        if (val < 0) {
            write_single('-');
            val = -val; // todo min
        }
        size_t len = 0;
        while (val) {
            small[len++] = char('0' + (val % 10));
            val /= 10;
        }
        for (size_t i = 0; i < len; i++) {
            line[pos + i] = small[len - 1 - i];
        }
        pos += len;
    }
    void write_single(const string& s) {
        for (char c : s) write_single(c);
    }
    void write_single(const char* s) {
        size_t len = strlen(s);
        for (size_t i = 0; i < len; i++) write_single(s[i]);
    }
    template <class T> void write_single(const V<T>& val) {
        auto n = val.size();
        for (size_t i = 0; i < n; i++) {
            if (i) write_single(' ');
            write_single(val[i]);
        }
    }
};




// bit op
int popcnt(uint x) { return __builtin_popcount(x); }
int popcnt(ull x) { return __builtin_popcountll(x); }
int bsr(uint x) { return 31 - __builtin_clz(x); }
int bsr(ull x) { return 63 - __builtin_clzll(x); }
int bsf(uint x) { return __builtin_ctz(x); }
int bsf(ull x) { return __builtin_ctzll(x); }

struct BitVec {
    static constexpr size_t B = 64;
    size_t n;
    V<ull> d;
    explicit BitVec(size_t _n = 0) : n(_n), d((n + B - 1) / B) {}
    void erase_last() {
        if (n % B) d.back() &= ull(-1) >> (B - n % B);
    }
    size_t size() const { return n; }
    bool operator[](size_t i) const { return (d[i / B] >> (i % B) & 1) != 0; }
    void set(size_t i, bool f = true) {
        if (f)
            d[i / B] |= 1ULL << (i % B);
        else
            d[i / B] &= ~(1ULL << (i % B));
    }
    void reset() { fill(d.begin(), d.end(), 0); }
    void reset(size_t i) { set(i, false); }
    void push_back(bool f) {
        if (n % B == 0) d.push_back(0);
        set(n, f);
        n++;
    }
    bool empty() const {
        for (auto& x : d)
            if (x) return false;
        return true;
    }

    size_t bsf() const {
        auto m = d.size();
        for (size_t i = 0; i < m; i++) {
            if (d[i]) return i * B + ::bsf(d[i]);
        }
        assert(false);
    }

    size_t count() const {
        size_t sm = 0;
        for (auto x : d) sm += popcnt(x);
        return sm;
    }

    void swap_elms(size_t a, size_t b) {
        bool f = (*this)[a];
        set(a, (*this)[b]);
        set(b, f);
    }

    template <class OP> BitVec& op1(OP op) {
        for (auto& x : d) x = op(x);
        return *this;
    }

    template <class OP> BitVec& op2(const BitVec& r, OP op) {
        assert(n == r.n);
        for (size_t i = 0; i < d.size(); i++) d[i] = op(d[i], r.d[i]);
        return *this;
    }

    BitVec& flip() {
        op1(bit_not<ull>());
        if (n % B) d.back() &= ~(-1ULL << (n % B));
        return *this;
    }
    BitVec& operator&=(const BitVec& r) { return op2(r, bit_and<ull>()); }
    BitVec& operator|=(const BitVec& r) { return op2(r, bit_or<ull>()); }
    BitVec& operator^=(const BitVec& r) { return op2(r, bit_xor<ull>()); }
    BitVec& operator<<=(const size_t& s) {
        auto block = s / B, rem = s % B;
        if (d.size() <= block) {
            reset();
            return *this;
        }
        for (size_t i = d.size() - 1; i > block; i--) {
            if (rem == 0)
                d[i] = d[i - block];
            else
                d[i] = d[i - block] << rem | d[i - block - 1] >> (B - rem);
        }
        d[block] = d[0] << rem;
        erase_last();
        fill(d.begin(), d.begin() + block, 0ULL);
        return *this;
    }
    BitVec& operator>>=(const size_t& s) {
        auto block = s / B, rem = s % B;
        if (d.size() <= block) {
            reset();
            return *this;
        }
        for (size_t i = 0; i < d.size() - block - 1; i++) {
            if (rem == 0)
                d[i] = d[i + block];
            else
                d[i] = d[i + block + 1] << (B - rem) | d[i + block] >> rem;
        }
        d[d.size() - block - 1] = d.back() >> rem;
        fill(d.begin() + d.size() - block, d.end(), 0ULL);
        return *this;
    }
    BitVec& operator~() const { return BitVec(*this).flip(); }
    BitVec operator&(const BitVec& r) const { return BitVec(*this) &= r; }
    BitVec operator|(const BitVec& r) const { return BitVec(*this) |= r; }
    BitVec operator^(const BitVec& r) const { return BitVec(*this) ^= r; }
    BitVec operator<<(const size_t& s) const { return BitVec(*this) <<= s; }
    BitVec operator>>(const size_t& s) const { return BitVec(*this) >>= s; }

    BitVec substr(size_t st, size_t le) const {
        assert(st + le <= n);
        BitVec res(le);
        size_t i = 0;
        while (i < le) {
            res.d[i / B] |= d[(st + i) / B] >> ((st + i) % B) << (i % B);
            i += min(B - i % B, B - (st + i) % B);
        }
        res.erase_last();
        return res;
    }
    bool substr_match(size_t st, const BitVec& pat) const {
        size_t le = pat.size();
        assert(st + le <= n);
        size_t i = 0;
        while (i < le) {
            size_t u = min({le - i, B - i % B, B - (st + i) % B});
            ull z = pat.d[i / B] >> (i % B) ^ d[(st + i) / B] >> ((st + i) % B);
            if (z << (B - u)) return false;
            i += u;
        }
        return true;
    }

    bool operator==(const BitVec& r) const { return d == r.d; }
};
ostream& operator<<(ostream& os, const BitVec& bs) {
    os << "B(";
    for (size_t i = 0; i < bs.size(); i++) {
        os << bs[i];
    }
    return os << ")";
}


template <class D> struct Mat : VV<D> {
    using VV<D>::VV;
    using VV<D>::size;
    int h() const { return int(size()); }
    int w() const { return int((*this)[0].size()); }
    Mat operator*(const Mat& r) const {
        assert(w() == r.h());
        Mat res(h(), V<D>(r.w()));
        for (int i = 0; i < h(); i++) {
            for (int j = 0; j < r.w(); j++) {
                for (int k = 0; k < w(); k++) {
                    res[i][j] += (*this)[i][k] * r[k][j];
                }
            }
        }
        return res;
    }
    Mat& operator*=(const Mat& r) { return *this = *this * r; }
    Mat pow(ll n) const {
        assert(h() == w());
        Mat x = *this, r(h(), V<D>(w()));
        for (int i = 0; i < h(); i++) r[i][i] = D(1);
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
};

template <class D> V<D> solve_linear(Mat<D> a, V<D> b, D eps) {
    int h = a.h(), w = a.w();
    int r = 0;
    V<int> idxs;
    for (int x = 0; x < w; x++) {
        for (int y = r + 1; y < h; y++) {
            D d = hypot(a[r][x], a[y][x]);
            if (abs(d) <= eps) continue;
            D c = a[r][x] / d, s = a[y][x] / d;
            auto rot = [&](D& u, D& v) {
                tie(u, v) = make_pair(c * u + s * v, c * v - s * u);
            };
            rot(b[r], b[y]);
            for (int k = x; k < w; k++) rot(a[r][k], a[y][k]);
        }
        if (a[r][x] <= eps) continue;
        r++;
        idxs.push_back(x);
        if (r == h) break;
    }
    V<D> v(w);
    for (int y = r - 1; y >= 0; y--) {
        int f = idxs[y];
        v[f] = b[y];
        for (int x = f + 1; x < w; x++) {
            v[f] -= a[y][x] * v[x];
        }
        v[f] /= a[y][f];
    }
    return v;
}

template <class Mint> V<Mint> solve_linear(Mat<Mint> a, V<Mint> b) {
    int h = a.h(), w = a.w();
    int r = 0;
    V<int> idxs;
    for (int x = 0; x < w; x++) {
        int my = -1;
        for (int y = r; y < h; y++) {
            if (a[y][x]) {
                my = y;
                break;
            }
        }
        if (my == -1) continue;
        if (r != my) swap(a[r], a[my]);
        swap(b[r], b[my]);
        for (int y = r + 1; y < h; y++) {
            if (!a[y][x]) continue;
            auto freq = a[y][x] / a[r][x];
            for (int k = x; k < w; k++) a[y][k] -= freq * a[r][k];
            b[y] -= freq * b[r];
        }
        r++;
        idxs.push_back(x);
        if (r == h) break;
    }
    V<Mint> v(w);
    for (int y = r - 1; y >= 0; y--) {
        int f = idxs[y];
        v[f] = b[y];
        for (int x = f + 1; x < w; x++) {
            v[f] -= a[y][x] * v[x];
        }
        v[f] /= a[y][f];
    }
    return v;
}

template <class Mint> int calc_rank(Mat<Mint> a) {
    int h = a.h(), w = a.w();
    int r = 0;
    V<int> idxs;
    for (int x = 0; x < w; x++) {
        int my = -1;
        for (int y = r; y < h; y++) {
            if (a[y][x]) {
                my = y;
                break;
            }
        }
        if (my == -1) continue;
        if (r != my) swap(a[r], a[my]);
        for (int y = r + 1; y < h; y++) {
            if (!a[y][x]) continue;
            auto freq = a[y][x] / a[r][x];
            for (int k = x; k < w; k++) a[y][k] -= freq * a[r][k];
        }
        r++;
        idxs.push_back(x);
        if (r == h) break;
    }
    return r;
}

template <class Mint> Mint calc_det(Mat<Mint> a) {
    assert(a.h() == a.w());
    int n = a.h();

    bool flip = false;
    for (int x = 0; x < n; x++) {
        int my = -1;
        for (int y = x; y < n; y++) {
            if (a[y][x]) {
                my = y;
                break;
            }
        }
        if (my == -1) return 0;
        if (x != my) {
            swap(a[x], a[my]);
            if ((x - my) % 2) flip = !flip;
        }
        for (int y = x + 1; y < n; y++) {
            if (!a[y][x]) continue;
            auto freq = a[y][x] / a[x][x];
            for (int k = x; k < n; k++) a[y][k] -= freq * a[x][k];
        }
    }
    Mint det = (!flip ? 1 : -1);
    for (int i = 0; i < n; i++) {
        det *= a[i][i];
    }
    return det;
}

template <class Mint> Mat<Mint> inverse(Mat<Mint> a) {
    assert(a.h() == a.w());
    int n = a.h();

    Mat<Mint> b(n, V<Mint>(n));
    for (int i = 0; i < n; i++) b[i][i] = 1;

    for (int x = 0; x < n; x++) {
        int my = -1;
        for (int y = x; y < n; y++) {
            if (a[y][x]) {
                my = y;
                break;
            }
        }
        if (my == -1) return {};
        if (x != my) {
            swap(a[x], a[my]);
            swap(b[x], b[my]);
        }
        auto freq = a[x][x];
        for (int j = 0; j < n; j++) {
            a[x][j] /= freq;
            b[x][j] /= freq;
        }
        for (int y = 0; y < n; y++) {
            if (x == y) continue;
            if (!a[y][x]) continue;
            freq = a[y][x];
            for (int k = 0; k < n; k++) a[y][k] -= freq * a[x][k];
            for (int k = 0; k < n; k++) b[y][k] -= freq * b[x][k];
        }
    }
    return b;
}

struct Mat2 : V<BitVec> {
    using V<BitVec>::V;
    using V<BitVec>::size;
    int h() const { return int(size()); }
    int w() const { return int((*this)[0].size()); }
    Mat2 operator*(const Mat2& r) const {
        assert(w() == r.h());
        Mat2 r_t = Mat2(r.h(), BitVec(r.w()));
        for (int y = 0; y < r_t.h(); y++) {
            for (int x = 0; x < r_t.w(); x++) {
                r_t[y].set(x, r[x][y]);
            }
        }
        Mat2 res(h(), BitVec(r_t.h()));
        for (int i = 0; i < h(); i++) {
            for (int j = 0; j < r_t.h(); j++) {
                res[i].set(j, ((*this)[i] ^ r_t[j]).count() % 2 == 1);
            }
        }
        return res;
    }
};

int calc_rank(Mat2 a) {
    int h = a.h(), w = a.w();
    int r = 0;
    V<int> idxs;
    for (int x = 0; x < w; x++) {
        int my = -1;
        for (int y = r; y < h; y++) {
            if (a[y][x]) {
                my = y;
                break;
            }
        }
        if (my == -1) continue;
        if (r != my) swap(a[r], a[my]);
        for (int y = r + 1; y < h; y++) {
            if (!a[y][x]) continue;
            a[y] ^= a[r];
        }
        r++;
        idxs.push_back(x);
        if (r == h) break;
    }
    return r;
}

BitVec solve_linear(Mat2 a, BitVec b) {
    int h = a.h(), w = a.w();
    int r = 0;
    V<int> idxs;
    for (int x = 0; x < w; x++) {
        int my = -1;
        for (int y = r; y < h; y++) {
            if (a[y][x]) {
                my = y;
                break;
            }
        }
        if (my == -1) continue;
        if (r != my) swap(a[r], a[my]);
        b.swap_elms(r, my);
        for (int y = r + 1; y < h; y++) {
            if (!a[y][x]) continue;
            a[y] ^= a[r];
            b.set(y, b[y] ^ b[r]);
        }
        r++;
        idxs.push_back(x);
        if (r == h) break;
    }
    BitVec v(w);
    for (int y = r - 1; y >= 0; y--) {
        int f = idxs[y];
        v.set(f, b[y]);
        for (int x = f + 1; x < w; x++) {
            v.set(f, v[f] ^ (a[y][x] && v[x]));
        }
    }
    return v;
}

Mat2 solve_linear(Mat2 a) {
    int h = a.h(), w = a.w();
    int r = 0;
    for (int x = 0; x < w; x++) {
        int my = -1;
        for (int y = r; y < h; y++) {
            if (a[y][x]) {
                my = y;
                break;
            }
        }
        if (my == -1) continue;
        if (r != my) swap(a[r], a[my]);
        for (int y = 0; y < h; y++) {
            if (y == r || !a[y][x]) continue;
            a[y] ^= a[r];
        }
        r++;
        if (r == h) break;
    }
          ;
    return a;
}








#include <cstdint>


#include <random>



#include <chrono>

struct Random {
  private:
    // Use xoshiro256**
    // Refereces: http://xoshiro.di.unimi.it/xoshiro256starstar.c
    static uint64_t rotl(const uint64_t x, int k) {
        return (x << k) | (x >> (64 - k));
    }

    std::array<uint64_t, 4> s;

    uint64_t next() {
        const uint64_t result_starstar = rotl(s[1] * 5, 7) * 9;

        const uint64_t t = s[1] << 17;

        s[2] ^= s[0];
        s[3] ^= s[1];
        s[1] ^= s[2];
        s[0] ^= s[3];

        s[2] ^= t;

        s[3] = rotl(s[3], 45);

        return result_starstar;
    }

    // random choice from [0, upper]
    uint64_t next(uint64_t upper) {
        if (!(upper & (upper + 1))) {
            // b = 00..0011..11
            return next() & upper;
        }
        int lg = 63 - __builtin_clzll(upper);
        uint64_t mask = (lg == 63) ? ~0ULL : (1ULL << (lg + 1)) - 1;
        while (true) {
            uint64_t r = next() & mask;
            if (r <= upper)
                return r;
        }
    }

  public:
    Random(uint64_t seed = 0) {
        // Use splitmix64
        // Reference: http://xoshiro.di.unimi.it/splitmix64.c
        for (int i = 0; i < 4; i++) {
            uint64_t z = (seed += 0x9e3779b97f4a7c15);
            z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
            z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
            s[i] = z ^ (z >> 31);
        }
    }

    // random choice from [lower, upper]
    template <class T>
    T uniform(T lower, T upper) {
        assert(lower <= upper);
        return T(lower + next(uint64_t(upper - lower)));
    }

    bool uniform_bool() { return uniform(0, 1) == 1; }

    double uniform01() {
        uint64_t v = next(1ULL << 63);
        return double(v) / (1ULL << 63);
    }

    // generate random lower string that length = n
    std::string lower_string(size_t n) {
        std::string res = "";
        for (size_t i = 0; i < n; i++) {
            res += uniform('a', 'z');
        }
        return res;
    }

    // random shuffle
    template <class Iter>
    void shuffle(Iter first, Iter last) {
        if (first == last) return;
        // Reference and edit:
        // cpprefjp - C++日本語リファレンス
        // (https://cpprefjp.github.io/reference/algorithm/shuffle.html)
        int len = 1;
        for (auto it = first + 1; it != last; it++) {
            len++;
            int j = uniform(0, len - 1);
            if (j != len - 1)
                iter_swap(it, first + j);
        }
    }

    // generate random permutation that length = n
    template <class T>
    std::vector<T> perm(size_t n) {
        std::vector<T> idx(n);
        std::iota(idx.begin(), idx.end(), T(0));
        shuffle(idx.begin(), idx.end());
        return idx;
    }

    template <class T>
    std::vector<T> choice(size_t n, T lower, T upper) {
        assert(n <= upper - lower + 1);
        std::set<T> res;
        while (res.size() < n) res.insert(uniform(lower, upper));
        return {res.begin(), res.end()};
    }
} global_gen;

Random get_random_gen() {
    return Random(chrono::steady_clock::now().time_since_epoch().count());
}

Scanner sc = Scanner(stdin);
Printer pr = Printer(stdout);

void solve(int n) {
    auto id = [&](int r, int c) {
        return r * n + c;
    };
    Mat2 mt;
    for (int i = 0; i < n; i++) {
        BitVec vec(n * n);
        for (int j = 0; j < n; j++) {
            vec.set(id(i, j));
        }
        mt.push_back(vec);
    }
    for (int i = 0; i < n; i++) {
        BitVec vec(n * n);
        for (int j = 0; j < n; j++) {
            vec.set(id(j, i));
        }
        mt.push_back(vec);
    }
    for (int k = 0; k < 2 * n - 1; k++) {
        BitVec vec(n * n);
        for (int i = 0; i < n; i++) {
            int j = k - i;
            if (0 <= j && j < n) vec.set(id(i, j));
        }
        mt.push_back(vec);
    }
    for (int k = -n + 1; k < n; k++) {
        BitVec vec(n * n);
        for (int i = 0; i < n; i++) {
            int j = i - k;
            if (0 <= j && j < n) vec.set(id(i, j));
        }
        mt.push_back(vec);
    }

    mt = solve_linear(mt);
    while (mt.back() == BitVec(n * n)) mt.pop_back();

    int k = int(mt.size());
    V<size_t> bsfs(k);
    for (int i = 0; i < k; i++) {
        bsfs[i] = mt[i].bsf();
    }

    int m;
    sc.read(m);
    auto gen = get_random_gen();
    V<ull> zob(n * n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            zob[id(i, j)] = gen.uniform(0ULL, ull(-1));
        }
    }
            ;
    V<ull> hs(m);
    for (int ph = 0; ph < m; ph++) {
        BitVec vec(n * n);
        for (int i = 0; i < n; i++) {
            string s;
            sc.read(s);
            for (int j = 0; j < n; j++) {
                if (s[j] == '#') vec.set(id(i, j));
            }
        }

        for (int i = 0; i < k; i++) {
            if (vec[bsfs[i]]) vec ^= mt[i];
        }


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (vec[id(i, j)]) hs[ph] ^= zob[id(i, j)];
            }
        }
    }
           ;
    for (int i = 0; i < m - 1; i++) {
        for (int j = i + 1; j < m; j++) {
            if (hs[i] == hs[j]) pr.write(1);
            else pr.write(0);
        }
        pr.writeln();
    }

/*    for (auto v: mt) {  
        if (v == BitVec(n * n)) continue;
        cout << "---print---" << endl;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (v[id(i, j)]) cout << "1";
                else cout << "0";
            }
            cout << endl;
        }
        cout << endl;
    }*/
}

int main() {
    int n;
    sc.read(n);
    solve(n);
//    for (int n = 1; n <= 20; n++) {
//        solve(n);
//    }
}
yukicoder

結果

テストケース

ソースコード
