結果
| 問題 | No.3742 Re: Verse X |
| コンテスト | |
| ユーザー |
 TKTYI
|
| 提出日時 | 2026-09-19 17:21:19 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 590 ms / 2,000 ms |
| + 151µs | |
| コード長 | 5,907 bytes |
| 記録 | |
| コンパイル時間 | 5,206 ms |
| コンパイル使用メモリ | 406,328 KB |
| 実行使用メモリ | 62,184 KB |
| 最終ジャッジ日時 | 2026-09-19 17:21:42 |
| 合計ジャッジ時間 | 17,027 ms |
|
ジャッジサーバーID （参考情報） |
judge4_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 57 |
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:65:46: warning: 'x' may be used uninitialized [-Wmaybe-uninitialized]
65 | rep(i,0,N)rep(j,0,N)if(S[i][j]=='#')x|=1ull<<(i*N+j);
| ~^~~~~~~~~~~~~~~
main.cpp:64:13: note: 'x' was declared here
64 | ull x;
| ^
ソースコード
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long int ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vvvl> vvvvl;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef vector<vvvb> vvvvb;
typedef pair<ll,ll> pl;
typedef pair<ll,pl> ppl;
typedef pair<ll,ppl> pppl;
typedef pair<ll,pppl> pppppl;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) begin(a),end(a)
#define sz(a) (int)(a).size()
#define F first
#define S second
#define bs(A,x) binary_search(all(A),x)
#define lb(A,x) (ll)(lower_bound(all(A),x)-A.begin())
#define ub(A,x) (ll)(upper_bound(all(A),x)-A.begin())
#define cou(A,x) (ll)(upper_bound(all(A),x)-lower_bound(all(A),x))
template<typename T>using min_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<class T>bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,T b){if(b<a){a=b;return 1;}return 0;}
//*
using mint=modint998244353;
const ll mod=998244353;
//*/
/*
using mint=modint1000000007;
const ll mod=1000000007;
//*/
//using mint=modint;
//*
typedef vector<mint> vm;
typedef vector<vm> vvm;
typedef vector<vvm> vvvm;
typedef vector<vvvm> vvvvm;
ostream&operator<<(ostream&os,mint a){os<<a.val();return os;}
istream&operator>>(istream&is,mint&a){int x;is>>x;a=mint(x);return is;}
//*/
template<typename T1,typename T2>ostream&operator<<(ostream&os,pair<T1,T2>p){os<<p.F<<" "<<p.S;return os;}
template<typename T1,typename T2>istream&operator>>(istream&is,pair<T1,T2>&p){is>>p.F>>p.S;return is;}
template<typename T>ostream&operator<<(ostream&os,vector<T>v){rep(i,0,sz(v))os<<v[i]<<(i+1!=sz(v)?" ":"");return os;}
template<typename T>istream&operator>>(istream&is,vector<T>&v){for(T&in:v)is>>in;return is;}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
ll N;cin>>N;
//N=500;
vector<string>S(N);
cin>>S;
//rep(i,0,N)S[i]=string(N,'#');
if(N<=8){
using ull=unsigned long long;
ull x;
rep(i,0,N)rep(j,0,N)if(S[i][j]=='#')x|=1ull<<(i*N+j);
vector<ull>B;
vector<ppl>Q;
rep(k,3,N+1)if(k%2)rep(i,0,N+1-k)rep(j,0,N+1-k){
ull b=0;
rep(x,0,k)b|=1ull<<((i+x)*N+(j+x));
rep(x,0,k)b|=1ull<<((i+k-1-x)*N+(j+x));
B.emplace_back(b);
Q.emplace_back(k,pl(i,j));
}
vector<ull>basis;
vector<ull>RE;
rep(i,0,sz(B)){
ull re=1ull<<i,b=B[i];
rep(j,0,sz(basis))if(chmin(b,b^basis[j]))re^=RE[j];
if(b)RE.emplace_back(re),basis.emplace_back(b);
}
ull re=0;
rep(i,0,sz(basis))if(chmin(x,x^basis[i]))re^=RE[i];
if(x){cout<<-1<<endl;return 0;}
vector<ppl>ans;
rep(i,0,sz(Q))if((re>>i)&1)ans.emplace_back(Q[i]);
cout<<sz(ans)<<endl;
for(auto[k,p]:ans)cout<<k/2<<" "<<p.F+1+k/2<<" "<<p.S+1+k/2<<endl;
return 0;
}
vvl I(N,vl(N,-1));
ll c=0;
rep(i,0,N)rep(j,0,N)if(min(i+0ll,N-1-i)<2||min(j+0ll,N-1-j)<2)if(min(i+0ll,N-1-i)<4&&min(j+0ll,N-1-j)<4)I[i][j]=c++;
vvl J(N,vl(N));
rep(i,0,N)rep(j,0,N)if(I[i][j]!=-1)J[i][j]=1ll<<I[i][j];
rep(i,4,N-4){
if(i%4==0)J[i][0]=(1ll<<I[2][0])|(1ll<<I[3][1]);
else if(i%4==1)J[i][0]=(1ll<<I[2][1])|(1ll<<I[3][0]);
else if(i%4==2)J[i][0]=1ll<<I[2][0];
else J[i][0]=1ll<<I[3][0];
J[i][1]=1ll<<I[(i-4)%2+2][1];
if(i%4==0)J[0][i]=(1ll<<I[0][2])|(1ll<<I[1][3]);
else if(i%4==1)J[0][i]=(1ll<<I[1][2])|(1ll<<I[0][3]);
else if(i%4==2)J[0][i]=1ll<<I[0][2];
else J[0][i]=1ll<<I[0][3];
J[1][i]=1ll<<I[1][(i-4)%2+2];
if(i%4==0)J[i][N-1]=(1ll<<I[2][N-1])|(1ll<<I[3][N-2]);
else if(i%4==1)J[i][N-1]=(1ll<<I[2][N-2])|(1ll<<I[3][N-1]);
else if(i%4==2)J[i][N-1]=1ll<<I[2][N-1];
else J[i][N-1]=1ll<<I[3][N-1];
J[i][N-2]=1ll<<I[(i-4)%2+2][N-2];
if(i%4==0)J[N-1][i]=(1ll<<I[N-1][2])|(1ll<<I[N-2][3]);
else if(i%4==1)J[N-1][i]=(1ll<<I[N-2][2])|(1ll<<I[N-1][3]);
else if(i%4==2)J[N-1][i]=1ll<<I[N-1][2];
else J[N-1][i]=1ll<<I[N-1][3];
J[N-2][i]=1ll<<I[N-2][(i-4)%2+2];
}
vl B;
vector<ppl>Q;
rep(k,3,N+1)if(k%2){
rep(i,0,N+1-k)rep(j,0,N+1-k){
if(i<=1||j<=1||i+k-1>=N-2||j+k-1>=N-2){
ll b=0;
rep(x,0,k)b^=J[i+x][j+x];
rep(x,0,k)if(x!=k/2)b^=J[i+k-1-x][j+x];
if(b){
B.emplace_back(b);
Q.emplace_back(k,pl(i,j));
}
}
}
}
ll x=0;
rep(i,0,N)rep(j,0,N)if(S[i][j]=='#')x^=J[i][j];
vl basis;
vvl E;
rep(i,0,sz(B)){
ll b=B[i];
vl e={i};
rep(j,0,sz(basis))if(chmin(b,b^basis[j])){
for(auto k:E[j])e.emplace_back(k);
}
if(b){
sort(all(e));
vl _e;
rep(i,0,sz(e)){
if(i+1<sz(e)&&e[i]==e[i+1])i++;
else _e.emplace_back(e[i]);
}
E.emplace_back(_e);
basis.emplace_back(b);
}
if(sz(basis)==48)break;
}
vb OP(sz(Q));
rep(i,0,sz(basis))if(chmin(x,x^basis[i]))for(auto j:E[i])OP[j]=!OP[j];
if(x){cout<<-1<<endl;return 0;}
vector<ppl>ans;
auto op=[&](ll k,ll x,ll y){
rep(z,0,k)S[x+z][y+z]='#'+'.'-S[x+z][y+z];
rep(z,0,k)if(z!=k/2)S[x+k-1-z][y+z]='#'+'.'-S[x+k-1-z][y+z];
ans.emplace_back(k,pl(x,y));
};
rep(i,0,sz(Q))if(OP[i]){
auto[k,p]=Q[i];
auto[x,y]=p;
op(k,x,y);
}
rrep(i,4,N-4){
if(S[i][0]=='#')op(3,i-2,0);
if(S[i][1]=='#')op(3,i-2,1);
if(S[0][i]=='#')op(3,0,i-2);
if(S[1][i]=='#')op(3,1,i-2);
if(S[i][N-1]=='#')op(3,i-2,N-3);
if(S[i][N-2]=='#')op(3,i-2,N-4);
if(S[N-1][i]=='#')op(3,N-3,i-2);
if(S[N-2][i]=='#')op(3,N-4,i-2);
}
rep(i,2,N-2)rep(j,2,N-2)if(S[i][j]=='#'){
op(3,i-2,j-2);
op(3,i,j-2);
op(3,i-2,j);
op(3,i,j);
op(5,i-2,j-2);
}
sort(all(ans));
vector<ppl>_ans;
rep(i,0,sz(ans)){if(i+1<sz(ans)&&ans[i]==ans[i+1])i++;else _ans.emplace_back(ans[i]);}
cout<<sz(_ans)<<endl;
for(auto[k,p]:_ans)cout<<k/2<<" "<<p.F+1+k/2<<" "<<p.S+1+k/2<<endl;
return 0;
}