結果

問題 No.3742 Re: Verse X
コンテスト
ユーザー 👑 Nachia
提出日時 2026-09-19 16:21:35
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 43 ms / 2,000 ms
+ 502µs
コード長 10,933 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,308 ms
コンパイル使用メモリ 138,068 KB
実行使用メモリ 12,196 KB
最終ジャッジ日時 2026-09-19 16:21:55
合計ジャッジ時間 5,293 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }

ll examine(ll n){
  V<V<ll>> idx(n, V<ll>(n, -1));
  ll idxi = 0;
  REP(i,n) REP(j,n) if((i+j)%2 == 0) idx[i][j] = idxi++;
  V<ll> basis;
  for(ll k=3; k<=n; k+=2) REP(i,n-k+1) REP(j,n-k+1) if((i+j)%2 == 0){
    ll q = 0;
    REP(x,k) q |= 1ll << idx[i+x][j+x];
    REP(x,k) q |= 1ll << idx[i+x][j+k-1-x];
    for(auto& a : basis) chmin(q, q ^ a);
    if(q){
      for(auto& a : basis) chmin(a, a ^ q);
      basis.push_back(q);
    }
  }
  sort(basis.begin(), basis.end());
  for(auto& a : basis) cout << bitset<64>(a) << endl;
  return idxi - basis.size();
}

bool judge_rough(ll N, V<string> S){
  REP(xx,4){
    ll cnt[2] = {};
    REP(i,N) if(S[0][i] == '#') cnt[i%2]++;
    REP(t,2) if(cnt[t] % 2 == 1) return false;
    V<string> buf(N);
    REP(i,N) REP(j,N) buf[j].push_back(S[i][j]);
    swap(S, buf);
  }
  return true;
}

#include <utility>

#include <cassert>
namespace nachia{

// ax + by = gcd(a,b)
// return ( x, - )
std::pair<long long, long long> ExtGcd(long long a, long long b){
    long long x = 1, y = 0;
    while(b){
        long long u = a / b;
        std::swap(a-=b*u, b);
        std::swap(x-=y*u, y);
    }
    return std::make_pair(x, a);
}

} // namespace nachia

namespace nachia{

template<unsigned int MOD>
struct StaticModint{
private:
    using u64 = unsigned long long;
    unsigned int x;
public:

    using my_type = StaticModint;
    template< class Elem >
    static Elem safe_mod(Elem x){
        if(x < 0){
            if(0 <= x+MOD) return x + MOD;
            return MOD - ((-(x+MOD)-1) % MOD + 1);
        }
        return x % MOD;
    }

    StaticModint() : x(0){}
    StaticModint(const my_type& a) : x(a.x){}
    StaticModint& operator=(const my_type&) = default;
    template< class Elem >
    StaticModint(Elem v) : x(safe_mod(v)){}
    unsigned int operator*() const { return x; }
    my_type& operator+=(const my_type& r) { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator+(const my_type& r) const { my_type res = *this; return res += r; }
    my_type& operator-=(const my_type& r) { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator-(const my_type& r) const { my_type res = *this; return res -= r; }
    my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; }
    my_type& operator*=(const my_type& r){ x = (u64)x * r.x % MOD; return *this; }
    my_type operator*(const my_type& r) const { my_type res = *this; return res *= r; }
    bool operator==(const my_type& r) const { return x == r.x; }
    my_type pow(unsigned long long i) const {
        my_type a = *this, res = 1;
        while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; }
        return res;
    }
    my_type inv() const { return my_type(ExtGcd(x, MOD).first); }
    unsigned int val() const { return x; }
    int hval() const { return int(x > MOD/2 ? x - MOD : x); }
    static constexpr unsigned int mod() { return MOD; }
    static my_type raw(unsigned int val) { auto res = my_type(); res.x = val; return res; }
    my_type& operator/=(const my_type& r){ return operator*=(r.inv()); }
    my_type operator/(const my_type& r) const { return operator*(r.inv()); }
};

} // namespace nachia
#include <ostream>

namespace nachia{

template<class Elem>
struct MatrixModulo{
private:
    int h;
    int w;
    std::vector<Elem> elems;
public:
    
    MatrixModulo(int new_h=0, int new_w=0)
        : h(new_h), w(new_w), elems(h*w, Elem(0)){}
    MatrixModulo(const MatrixModulo &) = default;
    int numRow() const { return h; }
    int numColumn() const { return w; }
    int height() const { return numRow(); }
    int width() const { return numColumn(); }
    typename std::vector<Elem>::iterator operator[](int y){ return elems.begin() + (y*w); }
    typename std::vector<Elem>::const_iterator operator[](int y) const { return elems.begin() + (y*w); }
    static MatrixModulo Identity(int n){
        auto res = MatrixModulo(n,n);
        for(int i=0; i<n; i++) res[i][i]=Elem(1);
        return res;
    }
    MatrixModulo transposed() const {
        auto res = MatrixModulo(w,h);
        for(int i=0; i<h; i++) for(int j=0; j<w; j++) res[j][i] = elems[i*w+j];
        return res;
    }
    void swapColumns(int x1, int x2){
        assert(0 <= x1 && x1 < numColumn());
        assert(0 <= x2 && x2 < numColumn());
        for(int y=0; y<numRow(); y++) std::swap((*this)[y][x1], (*this)[y][x2]);
    }
    void swapRows(int y1, int y2){
        assert(0 <= y1 && y1 < numRow());
        assert(0 <= y2 && y2 < numRow());
        for(int x=0; x<numColumn(); x++) std::swap((*this)[y1][x], (*this)[y2][x]);
    }
    MatrixModulo operator*(const MatrixModulo& r) const {
        assert(width() == r.height());
        auto res = MatrixModulo(h, r.w);
        for(int i=0; i<h; i++) for(int j=0; j<w; j++) for(int k=0; k<r.w; k++){
            res[i][k] += (*this)[i][j] * r[j][k];
        }
        return res;
    }
    std::vector<Elem> operator*(const std::vector<Elem>& r) const {
        assert(width() == int(r.size()));
        auto res = std::vector<Elem>(h);
        for(int i=0; i<h; i++) for(int j=0; j<w; j++){
            res[i] += (*this)[i][j] * r[j];
        }
        return res;
    }
    MatrixModulo& operator*=(const Elem& r){
        int z = (int)elems.size();
        for(int i=0; i<z; i++) elems[i] *= r;
        return *this;
    }
    Elem det() const {
        assert(height() == width());
        MatrixModulo g = *this;
        Elem ans = 1;
        for(int i=0; i<h; i++){
            int tg = -1;
            for(int j=i; j<h; j++){ if(g[j][i].val() != 0) tg = j; }
            if(tg == -1) return 0;
            if(tg != i) ans = -ans;
            for(int j=0; j<h; j++) std::swap(g[i][j], g[tg][j]);
            tg = i;
            ans *= g[i][i];
            Elem const_coeff = g[i][i].inv();
            for(int j=0; j<h; j++) g[i][j] *= const_coeff;
            for(int j=i+1; j<h; j++) for(int k=h-1; k>=i; k--) g[j][k] -= g[j][i] * g[i][k];
        }
        return ans;
    }
    int rank() const {
        if(height() == 0 || width() == 0) return 0;
        MatrixModulo g = *this;
        int y = 0;
        for(int d=0; d<w; d++){
            if(y == h) break;
            int tg = -1;
            for(int i=y; i<h; i++){ if(g[i][d].val() != 0){ tg = i; break; } }
            if(tg == -1) continue;
            for(int j=d; j<w; j++) std::swap(g[y][j], g[tg][j]);
            tg = y;
            Elem const_coeff = g[y][d].inv();
            for(int j=d; j<w; j++) g[y][j] *= const_coeff;
            for(int i=y+1; i<h; i++) for(int j=w-1; j>=d; j--) g[i][j] -= g[i][d] * g[y][j];
            y++;
        }
        return y;
    }
    MatrixModulo pow(unsigned long long i){
        auto a = *this;
        auto res = Identity(height());
        while(i){
            if(i%2) res = res * a;
            a = a * a; i /= 2;
        }
        return res;
    }

    friend std::ostream& operator<<(std::ostream& os, const MatrixModulo& a){
        int n = a.height(), m = a.width();
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(j) os << " ";
                os << a[i][j].val();
            } os << "\n";
        }
        return os;
    }
};


} // namespace nachia

namespace nachia{

template<class Elem>
MatrixModulo<Elem> LinearEquation(MatrixModulo<Elem> g){
    int w = g.numColumn(), h = g.numRow();
    int y = 0;
    std::vector<std::pair<int,int>> det_var;
    std::vector<int> rank_var;
    for (int d=0; d<w-1; d++) {
        int tg = -1;
        for (int i=y; i<h; i++) { if (g[i][d].val() != 0){ tg = i; break; } }
        if (tg == -1){ rank_var.push_back(d); continue; }
        for (int j=d; j<w; j++) std::swap(g[y][j], g[tg][j]);
        tg = y;
        Elem const_coeff = g[y][d].inv();
        for (int j=d; j<w; j++) g[y][j] *= const_coeff;
        for (int i=0; i<h; i++) if (i != y) for(int j=w-1; j>=d; j--) g[i][j] -= g[i][d] * g[y][j];
        det_var.push_back(std::make_pair(d,y));
        y++;
    }
    for (int i=y; i<h; i++) if (g[i][w-1].val() != 0) return MatrixModulo<Elem>(0,0);
    MatrixModulo<Elem> solution(1 + rank_var.size(), w);
    for (auto [x,i] : det_var) { solution[0][x] = -g[i][w-1]; }
    solution[0][w-1] = 1;
    for (int d=0; d<(int)rank_var.size(); d++) {
        int varid = rank_var[d];
        solution[d+1][varid] = -Elem(1);
        for (auto [x,i] : det_var) { solution[d+1][x] = g[i][varid]; }
    }
    return solution;
}

} // namespace nahica

using Mint = nachia::StaticModint<2>;

void testcase(){
  ll N; cin >> N;
  V<string> S(N);
  REP(i,N) cin >> S[i];
  
  V<tuple<ll,ll,ll>> ans;
  auto op = [&](ll y, ll x, ll k){
    ans.push_back({ k/2, y+k/2, x+k/2 });
    REP(i,k) S[y+i][x+i] ^= '#' ^ '.';
    REP(i,k) S[y+i][x+k-1-i] ^= '#' ^ '.';
    S[y+k/2][x+k/2] ^= '#' ^ '.';
  };

  if(!judge_rough(N, S)){ cout << "-1\n"; return; }

  while(N > 10){
    REP(i,N) if(S[N-1][i] == '#') op(N-3, i, 3);
    REP(i,N) if(S[i][N-1] == '#') op(i, N-3, 3);
    // for(auto a : S) cout << a << endl;
    REP(t,2){
      ll cnt = 0;
      REP(i,N) if(S[N-2][i] == '#' && (i+1) % 2 == t) cnt++;
      if(cnt % 2 == 1){ op(N-3, 0+t, 3); op(N-5, 2+t, 5); op(N-7, 0+t, 7); }
    }
    REP(t,2){
      ll cnt = 0;
      REP(i,N) if(S[i][N-2] == '#' && (i+1) % 2 == t) cnt++;
      if(cnt % 2 == 1){ op(0+t, N-3, 3); op(2+t, N-5, 5); op(0+t, N-7, 7); }
    }
    N--;
  }

  S.resize(N);
  REP(i,N) S[i].resize(N);

  // cout << judge_rough(N, S) << endl;

  auto idx = [&](ll y, ll x){ return y*N+x; };
  V<tuple<ll,ll,ll>> opinfo;
  for(ll k=3; k<=N; k+=2) REP(y,N-k+1) REP(x,N-k+1){
    opinfo.push_back({ x, y, k });
  }
  nachia::MatrixModulo<Mint> eq(N*N, opinfo.size() + 1);
  REP(i,N) REP(j,N) if(S[i][j] == '#') eq[idx(i,j)][opinfo.size()] = 1;
  REP(opi,opinfo.size()){
    auto [x,y,k] = opinfo[opi];
    REP(i,k) eq[idx(y+i, x+i)][opi] = 1;
    REP(i,k) eq[idx(y+i, x+k-1-i)][opi] = 1;
  }
  auto sol = nachia::LinearEquation(eq);
  if(sol.height() == 0){ cout << "-1\n"; return; }

  REP(i,opinfo.size()){
    auto [x,y,k] = opinfo[i];
    if(sol[0][i].val()) op(y,x,k);
  }

  sort(ans.begin(), ans.end());
  cout << ans.size() << "\n";
  for(auto [a,b,c] : ans){
    cout << a << " " << (b+1) << " " << (c+1) << "\n";
  }
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  // ll T; cin >> T; REP(t,T)
  testcase();
  return 0;
}
0