#1187903 (C++23) No.3742 Re: Verse X

• 問題: No.3742 Re: Verse X
• ユーザー: uruzunyaa
• 提出日時: 2026-09-19 04:33:31
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 49 ms / 2,000 ms
• コード長: 5,275 bytes
• コンパイル時間: 2,618 ms
• コンパイル使用メモリ: 360,664 KB
• 実行使用メモリ: 11,872 KB
• 最終ジャッジ日時: 2026-09-19 13:26:29
• 合計ジャッジ時間: 6,942 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 57

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct Op{int k,r,c;};
int N;
vector<vector<int>> a;
bool useop[4][505][505];

Op tf(Op o,int fr,int fc,int sw){
    if(sw) swap(o.r,o.c);
    if(fr) o.r=N-1-o.r;
    if(fc) o.c=N-1-o.c;
    return o;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>N;
    vector<string> s(N);
    for(auto &x:s) cin>>x;

    a.assign(N,vector<int>(N));
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) a[i][j]=(s[i][j]=='#');

    auto cells=[&](Op o){
        vector<pair<int,int>> v;
        for(int d=-o.k;d<=o.k;d++){
            v.push_back({o.r+d,o.c+d});
            if(d) v.push_back({o.r+d,o.c-d});
        }
        return v;
    };

    // 小さい N は普通に GF(2) ガウス消去
    if(N<=10){
        constexpr int B=256;
        vector<Op> op;

        for(int k=1;2*k<N;k++)
            for(int r=k;r+k<N;r++)
                for(int c=k;c+k<N;c++)
                    op.push_back({k,r,c});

        int D=N*N,M=op.size();
        array<bitset<B>,100> bs{};

        for(int i=0;i<M;i++){
            bitset<B> v;
            v[D+i]=1;

            for(auto [r,c]:cells(op[i])) v[r*N+c]=1;

            for(int p=0;p<D;p++) if(v[p]){
                if(bs[p].any()) v^=bs[p];
                else{
                    bs[p]=v;
                    break;
                }
            }
        }

        bitset<B> t;
        for(int r=0;r<N;r++) for(int c=0;c<N;c++)
            if(a[r][c]) t[r*N+c]=1;

        for(int p=0;p<D;p++) if(t[p]){
            if(!bs[p].any()){
                cout<<-1<<'\n';
                return 0;
            }
            t^=bs[p];
        }

        vector<Op> ans;
        for(int i=0;i<M;i++) if(t[D+i]) ans.push_back(op[i]);

        cout<<ans.size()<<'\n';
        for(auto o:ans) cout<<o.k<<' '<<o.r+1<<' '<<o.c+1<<'\n';
        return 0;
    }

    // 外周の8不変量
    for(int p=0;p<2;p++){
        int z[4]={};

        for(int i=p;i<N;i+=2){
            z[0]^=a[0][i];
            z[1]^=a[N-1][i];
            z[2]^=a[i][0];
            z[3]^=a[i][N-1];
        }

        if(z[0]|z[1]|z[2]|z[3]){
            cout<<-1<<'\n';
            return 0;
        }
    }

    auto put=[&](Op o){
        useop[o.k][o.r][o.c]^=1;

        for(int d=-o.k;d<=o.k;d++){
            a[o.r+d][o.c+d]^=1;
            if(d) a[o.r+d][o.c-d]^=1;
        }
    };

    auto run=[&](const vector<Op>& g,int fr=0,int fc=0,int sw=0){
        for(auto o:g) put(tf(o,fr,fc,sw));
    };

    // 2層目の角付近用
    const vector<Op> Q0={
        {3,3,4},{1,1,6},{1,6,1}
    };
    const vector<Op> Q1={
        {3,4,3},{1,1,6},{1,6,1}
    };

    // 最外周の角用
    const vector<Op> C={
        {1,1,3},{1,1,5},{1,2,2},
        {1,3,1},{1,5,1},{3,3,3}
    };

    // 上辺の (0,j),(0,j+2) 用、j=1,2,3
    const vector<Op> P[3]={
        {
            {1,1,4},{1,1,6},{1,2,1},{1,2,5},
            {1,4,1},{1,5,2},{1,6,1},{3,3,4},{3,4,3}
        },
        {
            {1,1,5},{1,1,7},{1,2,4},{3,3,5}
        },
        {
            {1,1,2},{1,1,6},{1,3,2},{1,5,2},{3,3,4}
        }
    };

    // 2層目の、角付近以外を直接消す
    for(int r=0;r<N;r++) for(int c=0;c<N;c++){
        if(min({r,c,N-1-r,N-1-c})!=1) continue;

        bool sp=
            ((r==1||r==N-2)&&(c==2||c==N-3))||
            ((c==1||c==N-2)&&(r==2||r==N-3));

        if(!sp&&a[r][c]) put({1,r,c});
    }

    // 2層目の角付近8マス
    for(int fr=0;fr<2;fr++) for(int fc=0;fc<2;fc++){
        int r=fr?N-2:1,c=fc?N-3:2;
        if(a[r][c]) run(Q0,fr,fc);

        r=fr?N-3:2;
        c=fc?N-2:1;
        if(a[r][c]) run(Q1,fr,fc);
    }

    // 四隅
    for(int fr=0;fr<2;fr++) for(int fc=0;fc<2;fc++){
        int r=fr?N-1:0,c=fc?N-1:0;
        if(a[r][c]) run(C,fr,fc);
    }

    // 上,下,左,右 への変換
    int T[4][3]={
        {0,0,0},
        {1,0,0},
        {0,0,1},
        {0,1,1}
    };

    auto pairput=[&](int j,int side){
        int fr=T[side][0],fc=T[side][1],sw=T[side][2];

        if(j<=3||j>=N-6){
            int q=(j<=3?j:N-3-j);
            int mir=(j>=N-6);

            for(auto o:P[q-1])
                put(tf(tf(o,0,mir,0),fr,fc,sw));
        }
        else{
            vector<Op> g={
                {3,3,j+1},
                {1,1,j-1},
                {1,1,j+3}
            };
            run(g,fr,fc,sw);
        }
    };

    auto point=[&](int j,int side){
        return tf({0,0,j},T[side][0],T[side][1],T[side][2]);
    };

    // 最外周を各辺ごとに2マスずつ送って消す
    for(int side=0;side<4;side++){
        for(int j=1;j<=N-4;j++){
            Op p=point(j,side);
            if(a[p.r][p.c]) pairput(j,side);
        }
    }

    // 内部は5操作で1マスだけ反転
    for(int r=2;r<=N-3;r++) for(int c=2;c<=N-3;c++){
        if(!a[r][c]) continue;

        put({2,r,c});
        put({1,r-1,c-1});
        put({1,r-1,c+1});
        put({1,r+1,c-1});
        put({1,r+1,c+1});
    }

    vector<Op> ans;

    for(int k=1;k<=3;k++)
        for(int r=0;r<N;r++)
            for(int c=0;c<N;c++)
                if(useop[k][r][c])
                    ans.push_back({k,r,c});

    cout<<ans.size()<<'\n';
    for(auto o:ans)
        cout<<o.k<<' '<<o.r+1<<' '<<o.c+1<<'\n';
}