結果

問題 No.3232 Not Tic Tac Toe
ユーザー tatesoto
提出日時 2025-08-09 16:37:06
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,892 bytes
コンパイル時間 6,328 ms
コンパイル使用メモリ 334,180 KB
実行使用メモリ 20,512 KB
最終ジャッジ日時 2025-08-09 16:37:16
合計ジャッジ時間 9,831 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#include <iostream>
template <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {return os<<'(' <<p.first<<", "<<p.second<<')';}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {os<<'[';for(auto it=v.begin();it!=v.end();++it){os<<*it; if(next(it)!=v.end()){os<<", ";}}return os<<']';}
template <typename T>
ostream& operator<<(ostream& os, const vector<vector<T>>& vv) {os<<"[\n";for(auto it=vv.begin();it!=vv.end();++it){os<<"  "<<*it;if(next(it)!=vv.end()){os<<",\n";}else{os<<"\n";}}return os<<"]";}
#define dump(x) cerr << #x << " = " << (x) << '\n'
#else
#define dump(x) (void)0
#endif
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
template<class T> using pq = priority_queue<T>;
template<class T> using pq_g = priority_queue<T, vector<T>, greater<T>>;
#define out(x) cout<<x<<'\n'
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define OVERLOAD_REP(_1,_2,_3,name,...) name
#define REP1(i,n) for (auto i = std::decay_t<decltype(n)>{}; (i) != (n); ++(i))
#define REP2(i, l, r) for (auto i = (l); (i) != (r); ++(i))
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
template<class T> inline bool chmin(T& a, T b) {if(a > b){a = b; return true;} else {return false;}};
template<class T> inline bool chmax(T& a, T b) {if(a < b){a = b; return true;} else {return false;}};
const ll INF=(1LL<<60);
const ll mod=998244353;
using Graph = vector<vector<ll>>;
using Network = vector<vector<pair<ll,ll>>>;
using Grid = vector<string>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int dx2[8] = {1, 1,  1, 0,  0, -1, -1, -1};
const int dy2[8] = {1, 0, -1, 1, -1,  1,  0, -1};

static constexpr int MAXW = 10000;
using BS = bitset<MAXW>;

void solve() {
    int H,W; if(!(cin>>H>>W)) return;
    if (W > MAXW) {
        vector<string> g(H, string(W,'X'));
        auto ok = [&](int y,int x,char ch) -> bool {
            if (x>=2 && g[y][x-1]==ch && g[y][x-2]==ch) return false;
            if (y>=2 && g[y-1][x]==ch && g[y-2][x]==ch) return false;
            if (y>=2 && x>=2 && g[y-1][x-1]==ch && g[y-2][x-2]==ch) return false;
            if (y>=2 && x+2<W && g[y-1][x+1]==ch && g[y-2][x+2]==ch) return false;
            return true;
        };
        rep(y,H) rep(x,W){
            if (ok(y,x,'O')) g[y][x]='O';
            else g[y][x]='X';
        }
        rep(y,H) out(g[y]);
        return;
    }
    vector<string> g(H, string(W,'X'));
    function<bool(int,const BS&,const BS&)> build_row = [&](int y, const BS& p1, const BS& p2) -> bool {
        vector<int> cur(W,-1);
        BS rowBits;
        function<bool(int)> dfs = [&](int x) -> bool {
            if (x==W){
                for(int i=0;i<W;++i) g[y][i]=rowBits.test(i)?'O':'X';
                if (y==H-1) return true;
                return build_row(y+1,rowBits,p1);
            }
            for (int c : {0,1}){
                if (x>=2 && cur[x-1]==c && cur[x-2]==c) continue;
                if (y>=2 && (int)p1.test(x)==c && (int)p2.test(x)==c) continue;
                if (y>=2 && x>=2 && (int)p1.test(x-1)==c && (int)p2.test(x-2)==c) continue;
                if (y>=2 && x+2<W && (int)p1.test(x+1)==c && (int)p2.test(x+2)==c) continue;
                cur[x]=c;
                if (c) rowBits.set(x); else rowBits.reset(x);
                if (dfs(x+1)) return true;
                cur[x]=-1;
            }
            return false;
        };
        return dfs(0);
    };
    BS zero;
    build_row(0, zero, zero);
    rep(y,H) out(g[y]);
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}
0