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

提出ソース

結果

問題	No.2257 Swim and Sleep
ユーザー	noya2
提出日時	2023-03-15 02:27:14
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	139 ms / 2,000 ms
コード長	8,607 bytes
コンパイル時間	3,282 ms
コンパイル使用メモリ	244,648 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-09-18 15:38:30
合計ジャッジ時間	5,501 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	3 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	129 ms 5,376 KB
testcase_04	AC	127 ms 5,376 KB
testcase_05	AC	115 ms 5,376 KB
testcase_06	AC	139 ms 5,376 KB
testcase_07	AC	32 ms 5,376 KB
testcase_08	AC	34 ms 5,376 KB
testcase_09	AC	32 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	3 ms 5,376 KB
testcase_13	AC	3 ms 5,376 KB
testcase_14	AC	3 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB

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

ソースコード

raw source code

#include<bits/stdc++.h>
#include<atcoder/modint>
#define rep(i,n) for (int i = 0; i < int(n); ++i)
using namespace std;
using P = pair<int,int>;
using mint = atcoder::modint998244353;

void solve(){
    int h, w, k; cin >> h >> w >> k;
    int g = __gcd(h,w);
    if (k == 0){
        mint ans = mint(2).pow(h) + mint(2).pow(w) + mint(2).pow(g+2);
        if (g % 2 == 1){
            ans -= 8;
        }
        else {
            ans += mint(2).pow(h+w+1);
            if (g % 4 == 0){
                ans += 32;
            }
            else {
                ans -= 16;
            }
        }
        cout << ans.val() << endl;
        return ;
    }
    vector<int> xs(k), ys(k), ds(k);
    rep(i,k){
        cin >> xs[i] >> ys[i];
        char c; cin >> c;
        ds[i] = (c == 'U' ? 0 : c == 'L' ? 1 : c == 'D' ? 2 : 3);
    }
    auto number_of_sort = [&](map<int,int> &mp){
        vector<int> dcnt(4,0);
        for (auto p : mp) dcnt[p.second]++;
        int res = 0;
        rep(i,4) if (dcnt[i] > 0) res++;
        return res;
    };
    auto Case1 = [&](){
        vector<int> dcnt(4,0);
        rep(i,k) dcnt[ds[i]]++;
        int ver = dcnt[0] + dcnt[2], hor = dcnt[1] + dcnt[3];
        if (ver > 0 && hor > 0) return mint(0);
        if (ver > 0){
            map<int,int> mx;
            rep(i,k){
                if (mx.find(xs[i]) == mx.end()){
                    mx[xs[i]] = ds[i];
                }
                else if (mx[xs[i]] != ds[i]){
                    return mint(0);
                }
            }
            int siz = mx.size();
            return mint(2).pow(h-siz);
        }
        if (hor > 0){
            map<int,int> my;
            rep(i,k){
                if (my.find(ys[i]) == my.end()){
                    my[ys[i]] = ds[i];
                }
                else if (my[ys[i]] != ds[i]){
                    return mint(0);
                }
            }
            int siz = my.size();
            return mint(2).pow(w-siz);
        }
        return mint(0);
    };

    auto Case2 = [&](){
        if (g % 2 == 1) return mint(0);
        vector<int> dcnt0(4,0), dcnt1(4,0);
        rep(i,k){
            ((xs[i]+ys[i])%2 == 0 ? dcnt0 : dcnt1)[ds[i]]++;
        }
        int ver0 = dcnt0[0] + dcnt0[2], hor0 = dcnt0[1] + dcnt0[3];
        int ver1 = dcnt1[0] + dcnt1[2], hor1 = dcnt1[1] + dcnt1[3];
        if (ver0 > 0 && hor0 > 0) return mint(0);
        if (ver1 > 0 && hor1 > 0) return mint(0);
        if (ver0 > 0 && ver1 > 0) return mint(0);
        if (hor0 > 0 && hor1 > 0) return mint(0);
        if (ver0 > 0 || hor1 > 0){
            map<int,int> mx, my;
            rep(i,k){
                if ((xs[i]+ys[i]) % 2 == 0){
                    if (mx.find(xs[i]) == mx.end()){
                        mx[xs[i]] = ds[i];
                    }
                    else if (mx[xs[i]] != ds[i]){
                        return mint(0);
                    }
                }
                else {
                    if (my.find(ys[i]) == my.end()){
                        my[ys[i]] = ds[i];
                    }
                    else if (my[ys[i]] != ds[i]){
                        return mint(0);
                    }
                }
            }
            int sizx = mx.size(), sizy = my.size();
            mint res = mint(2).pow(h-sizx+w-sizy);
            res -= (2 - number_of_sort(mx)) * (2 - number_of_sort(my));
            return res;
        }
        if (hor0 > 0 || ver1 > 0){
            map<int,int> mx, my;
            rep(i,k){
                if ((xs[i]+ys[i]) % 2 == 1){
                    if (mx.find(xs[i]) == mx.end()){
                        mx[xs[i]] = ds[i];
                    }
                    else if (mx[xs[i]] != ds[i]){
                        return mint(0);
                    }
                }
                else {
                    if (my.find(ys[i]) == my.end()){
                        my[ys[i]] = ds[i];
                    }
                    else if (my[ys[i]] != ds[i]){
                        return mint(0);
                    }
                }
            }
            int sizx = mx.size(), sizy = my.size();
            mint res = mint(2).pow(h-sizx+w-sizy);
            res -= (2 - number_of_sort(mx)) * (2 - number_of_sort(my));
            return res;
        }
        return mint(0);
    };

    mint ans = Case1() + Case2();

    bool modgok = true;
    map<P,int> mgok;
    rep(i,k){
        xs[i] %= g, ys[i] %= g;
        if (mgok.find(P(xs[i],ys[i])) == mgok.end()){
            mgok[P(xs[i],ys[i])] = ds[i];
        }
        else if (mgok[P(xs[i],ys[i])] != ds[i]){
            modgok = false;
        }
    }
    if (!modgok){
        cout << ans.val() << endl;
        return ;
    }
    auto mod = [&](int xy){
        return (xy%g+g)%g;
    };
    auto Case3 = [&](){
        vector<int> dcnt(4,0);
        rep(i,k) dcnt[ds[i]]++;
        int nonzero = 0, id1 = -1, id2 = -1;
        rep(i,4){
            if (dcnt[i] > 0){
                nonzero++;
                if (id1 == -1) id1 = i;
                else if (id2 == -1) id2 = i;
            }
        }
        if (nonzero >= 3) return mint(0);
        if (id2 != -1){
            if ((id1 != 0 || id2 != 1) && (id1 != 2 || id2 != 3)){
                return mint(0);
            }
        }
        map<int,int> xmy;
        rep(i,k){
            int ixmy = mod(xs[i]-ys[i]);
            if (xmy.find(ixmy) == xmy.end()){
                xmy[ixmy] = ds[i];
            }
            else if (xmy[ixmy] != ds[i]){
                return mint(0);
            }
        }
        int siz = xmy.size();
        return mint(2).pow(g-siz) - 2 + nonzero;
    };
    auto Case4 = [&](){
        vector<int> dcnt(4,0);
        rep(i,k) dcnt[ds[i]]++;
        int nonzero = 0, id1 = -1, id2 = -1;
        rep(i,4){
            if (dcnt[i] > 0){
                nonzero++;
                if (id1 == -1) id1 = i;
                else if (id2 == -1) id2 = i;
            }
        }
        if (nonzero >= 3) return mint(0);
        if (id2 != -1){
            if ((id1 != 0 || id2 != 3) && (id1 != 1 || id2 != 2)){
                return mint(0);
            }
        }
        map<int,int> xpy;
        rep(i,k){
            int ixpy = mod(xs[i]+ys[i]);
            if (xpy.find(ixpy) == xpy.end()){
                xpy[ixpy] = ds[i];
            }
            else if (xpy[ixpy] != ds[i]){
                return mint(0);
            }
        }
        int siz = xpy.size();
        return mint(2).pow(g-siz) - 2 + nonzero;
    };
    ans += Case3() + Case4();
    if (g % 4 != 0){
        cout << ans.val() << endl;
        return ;
    }
    auto Case5 = [&](){
        vector<vector<int>> m4(4,vector<int>(4,-1));
        rep(i,k){
            xs[i] %= 4, ys[i] %= 4;
            if (m4[xs[i]][ys[i]] == -1){
                m4[xs[i]][ys[i]] = ds[i];
            }
            else if (m4[xs[i]][ys[i]] != ds[i]){
                return mint(0);
            }
        }
        vector<vector<int>> tmp1 = 
        {
            {0, 3, 1, 3},
            {1, 3, 1, 2},
            {1, 3, 0, 3},
            {1, 2, 1, 3}
        };
        vector<vector<int>> tmp2 = 
        {
            {1, 0, 1, 3},
            {1, 3, 2, 3},
            {1, 3, 1, 0},
            {2, 3, 1, 3}
        };
        vector<vector<int>> tmp3 = 
        {
            {0, 0, 0, 3},
            {1, 2, 2, 2},
            {0, 3, 0, 0},
            {2, 2, 1, 2}
        };
        vector<vector<int>> tmp4 = 
        {
            {1, 0, 0, 0},
            {2, 2, 2, 3},
            {0, 0, 1, 0},
            {2, 3, 2, 2}
        };
        vector<vector<int>> tmp5 =
        {
            {0, 0, 1, 3},
            {1, 3, 2, 2},
            {1, 3, 0, 0},
            {2, 2, 1, 3}
        };
        vector<vector<int>> tmp6 = 
        {
            {1, 0, 0, 3},
            {1, 2, 2, 3},
            {0, 3, 1, 0},
            {2, 3, 1, 2}  
        };
        vector<vector<vector<int>>> tmp = {tmp1,tmp2,tmp3,tmp4,tmp5,tmp6};
        auto match = [&](vector<vector<int>> &test, int ex, int ey){
            rep(x,4) rep(y,4){
                if (m4[x][y] == -1 || m4[x][y] == test[(x+ex)%4][(y+ey)%4]){
                    continue;
                }
                return false;
            }
            return true;
        };
        mint res = 0;
        rep(i,6) rep(ex,4) rep(ey,2) if (match(tmp[i],ex,ey)) res++;
        return res;
    };
    ans += Case5();
    cout << ans.val() << endl;
}

int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int t = 1; cin >> t;
    while(t--) solve();
}

yukicoder

結果

テストケース

ソースコード