結果
| 問題 |
No.1056 2D Lamps
|
| コンテスト | |
| ユーザー |
 yosupot
|
| 提出日時 | 2020-05-15 22:41:05 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 272 ms / 3,000 ms |
| コード長 | 22,508 bytes |
| コンパイル時間 | 2,183 ms |
| コンパイル使用メモリ | 145,084 KB |
| 最終ジャッジ日時 | 2025-01-10 11:54:22 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 14 |
ソースコード
//#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);
// }
}