#851959 (C++17) No.2257 Swim and Sleep

提出ソース

結果

問題	No.2257 Swim and Sleep
ユーザー	👑 Nachia
提出日時	2023-03-24 03:49:31
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	125 ms / 2,000 ms
コード長	7,788 bytes
コンパイル時間	1,590 ms
コンパイル使用メモリ	111,360 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-09-18 15:51:13
合計ジャッジ時間	3,085 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	104 ms 6,940 KB
testcase_04	AC	117 ms 6,940 KB
testcase_05	AC	105 ms 6,940 KB
testcase_06	AC	125 ms 6,940 KB
testcase_07	AC	54 ms 6,940 KB
testcase_08	AC	59 ms 6,944 KB
testcase_09	AC	56 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	2 ms 6,940 KB
testcase_16	AC	2 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <atcoder/modint>
using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
const i64 INF = 1001001001001001001;

using Modint = atcoder::static_modint<998244353>;

int GCD(int a, int b){ return b ? GCD(b,a%b) : a; }

void CoordCompress(vector<int>& ar){
    vector<int> T = ar;
    sort(T.begin(), T.end());
    for(auto& a : ar) a = lower_bound(T.begin(), T.end(), a) - T.begin();
}

bool CollideTrivial(int H, int W, int K, vector<int> X, vector<int> Y, vector<int> D){
    map<int, int> Xset, Yset;
    rep(k,K){
        switch (D[k]) {
        case 0: { Yset[Y[k]] |= 1; } break;
        case 1: { Xset[X[k]] |= 1; } break;
        case 2: { Yset[Y[k]] |= 2; } break;
        case 3: { Xset[X[k]] |= 2; } break;
        }
    }
    for(auto q : Xset) if(q.second == 3) return true;
    for(auto q : Yset) if(q.second == 3) return true;
    return false;
}

void Unique(vector<int>& A){
    sort(A.begin(), A.end());
    A.erase(unique(A.begin(), A.end()), A.end());
}

Modint Alternate(int H, int W, int K, vector<int> X, vector<int> Y, vector<int> D, vector<int> Dcnt){
    if(H%2 != 0 || W%2 != 0) return 0;
    vector<int> Xset;
    vector<int> Yset;
    int en = 3;
    rep(k,K){
        switch (D[k]) {
        case 0: { Yset.push_back(Y[k]); } break;
        case 1: { Xset.push_back(X[k]); } break;
        case 2: { Yset.push_back(Y[k]); } break;
        case 3: { Xset.push_back(X[k]); } break;
        }
        int ty = 0;
        if(D[k] & 1) ty ^= 1;
        ty ^= X[k] & 1;
        ty ^= Y[k] & 1;
        en &= ~(1 << ty);
    }
    if(en == 0) return 0;

    Unique(Yset);
    Unique(Xset);

    long long powC = 0;
    powC += H;
    powC += W;
    powC -= Yset.size();
    powC -= Xset.size();

    Modint ans = Modint(2).pow(powC);
    if(Dcnt[0] == 0 && Dcnt[1] == 0) ans -= 1;
    if(Dcnt[1] == 0 && Dcnt[2] == 0) ans -= 1;
    if(Dcnt[2] == 0 && Dcnt[3] == 0) ans -= 1;
    if(Dcnt[3] == 0 && Dcnt[0] == 0) ans -= 1;
    if(en == 3) ans *= 2;

    return ans;
}

Modint Diagonal(int H, int W, int K, vector<int> X, vector<int> Y, vector<int> D, vector<int> Dcnt){
    // into G x G grid
    int G = GCD(H, W);
    for(int& x : X) x %= G;
    for(int& y : Y) y %= G;
    Modint ans = 0;

    if(G == 1) return 0;

    rep(t,2){
        // reverse y-axis
        for(int& y : Y) y = G-1-y;
        swap(Dcnt[1], Dcnt[3]);
        for(int& d : D) if(d%2 == 1) d ^= 2;

        map<int, int> lineSet;
        rep(k,K){
            int line = (X[k] + Y[k]) % G;
            lineSet[line] |= 1 << D[k];
        }

        // instructed to 2 direction in a same group (invalid)
        bool ok = true;
        for(auto a : lineSet){
            int cnt = 0;
            rep(d,4) cnt += (a.second >> d) & 1;
            if(cnt > 1){ ok = false; break; }
        }
        if(!ok) continue;

        Modint tmp = Modint(2).pow(G - lineSet.size());
        if(Dcnt[0] == 0 && Dcnt[1] == 0){
            ans += tmp; // no left down
            if(Dcnt[2] == K) ans -= 1; // all same direction
            if(Dcnt[3] == K) ans -= 1; // all same direction
        }
        if(Dcnt[2] == 0 && Dcnt[3] == 0){
            ans += tmp; // no right up
            if(Dcnt[0] == K) ans -= 1; // all same direction
            if(Dcnt[1] == K) ans -= 1; // all same direction
        }
    }

    return ans;
}

Modint Parallel(int H, int W, int K, vector<int> X, vector<int> Y, vector<int> D, vector<int> Dcnt){
    Unique(X);
    Unique(Y);
    Modint ans = 0;
    // no left right
    if(Dcnt[0] == 0 && Dcnt[2] == 0){
        ans += Modint(2).pow(H - X.size());
    }
    // no up down
    if(Dcnt[1] == 0 && Dcnt[3] == 0){
        ans += Modint(2).pow(W - Y.size());
    }
    return ans;
}

Modint DivBy4Case(int H, int W, int K, vector<int> X, vector<int> Y, vector<int> D){
    if(H % 4 != 0) return 0;
    if(W % 4 != 0) return 0;
    for(int& x : X) x %= 4;
    for(int& y : Y) y %= 4;
    int mode[4][4] = {};
    rep(i,4) rep(j,4) mode[i][j] = -1;
    rep(k,K) mode[Y[k]][X[k]] = D[k];
    rep(k,K) if(mode[Y[k]][X[k]] >= 0 && mode[Y[k]][X[k]] != D[k]) return 0;

    Modint ans = 0;

    vector<vector<int>> pat1V = {
        {1,0,0,0},
        {0,1,0,0},
        {0,0,1,0},
        {0,0,0,1}
    };
    rep(y,4) rep(x,4) pat1V[y][x] += (pat1V[y][x] ? x : y) % 2 * 2;
    rep(t0,2){
        rep(t1,2){
            rep(dy,2) rep(dx,4){
                int pat1[4][4] = {};
                rep(y,4) rep(x,4) pat1[(y+dy)%4][(x+dx)%4] = pat1V[y][x];

                bool ok = true;
                rep(i,4) rep(j,4) if(mode[i][j] >= 0 && mode[i][j] != pat1[i][j]) ok = false;
                if(ok) ans += 1;

                int B[4][4] = {};
                rep(y,4) rep(x,4){
                    if(pat1[y][x] == 0) B[y][(x+3)%4] = 1;
                    if(pat1[y][x] == 1) B[(y+3)%4][x] = 1;
                    if(pat1[y][x] == 2) B[y][(x+1)%4] = 1;
                    if(pat1[y][x] == 3) B[(y+1)%4][x] = 1;
                }
            }
            reverse(pat1V.begin(), pat1V.end());
            rep(i,4) rep(j,4) if(pat1V[i][j] % 2 == 1) pat1V[i][j] ^= 2;
        }
        rep(i,4) rep(j,4) if(i<j) swap(pat1V[i][j], pat1V[j][i]);
        rep(i,4) rep(j,4) pat1V[i][j] ^= 1;
    }

    
    vector<vector<int>> pat2V = {
        {1,1,0,0},
        {1,1,0,0},
        {0,0,1,1},
        {0,0,1,1}
    };
    rep(y,4) rep(x,4) pat2V[y][x] += (pat2V[y][x] ? x : y) % 2 * 2;
    rep(t1,2){
        rep(dy,2) rep(dx,4){
            int pat2[4][4] = {};
            rep(y,4) rep(x,4) pat2[(y+dy)%4][(x+dx)%4] = pat2V[y][x];

            bool ok = true;
            rep(i,4) rep(j,4) if(mode[i][j] >= 0 && mode[i][j] != pat2[i][j]) ok = false;
            if(ok) ans += 1;

            int B[4][4] = {};
            rep(y,4) rep(x,4){
                if(pat2[y][x] == 0) B[y][(x+3)%4] = 1;
                if(pat2[y][x] == 1) B[(y+3)%4][x] = 1;
                if(pat2[y][x] == 2) B[y][(x+1)%4] = 1;
                if(pat2[y][x] == 3) B[(y+1)%4][x] = 1;
            }
        }
        rep(i,4) rep(j,4) pat2V[i][j] ^= 2;
    }

    return ans;
}

// we can decide :
//     choose one of DU for each x
//     choose one of LR for each y
//     choose horizontal or vertical for each mass
// to find patterns

Modint testcase(){
    // H is HORIZONTAL size ( x coord range, LR move range )
    // W is VERTICAL size ( y coord range, DU move range )
    int H, W, K; cin >> H >> W >> K;

    vector<int> X(K), Y(K), D(K);
    vector<int> Dcnt(4);
    rep(k,K){
        int x,y; char d; cin >> x >> y >> d;
        X[k] = x;
        Y[k] = y;
        // I mean,
        //    bit 0 : 1=vertical, 0=horizontal
        //    bit 1 : 1=increasing, 0=decreasing
        if(d == 'L') D[k] = 0;
        if(d == 'D') D[k] = 1;
        if(d == 'R') D[k] = 2;
        if(d == 'U') D[k] = 3;
        Dcnt[D[k]]++;
    }
    if(CollideTrivial(H,W,K,X,Y,D)) return 0;

    if(H == 1 && W == 1){
        if(K == 0) return 4;
        return 1;
    }

    Modint ans = 0;
    ans += Alternate(H, W, K, X, Y, D, Dcnt); // 2x2 complex pattern but not Diagonal case
    ans += Diagonal(H, W, K, X, Y, D, Dcnt); // fixed direction in a diagonal, but not all same
    ans += Parallel(H, W, K, X, Y, D, Dcnt); // all moves are parallel to each other
    ans += DivBy4Case(H, W, K, X, Y, D); // 4x4 very complex case
    return ans;
}

int main(){
    int T; cin >> T;
    rep(t,T) cout << testcase().val() << '\n';
    return 0;
}



struct ios_do_not_sync{
    ios_do_not_sync(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;

yukicoder

結果

テストケース

ソースコード