結果

問題 No.359 門松行列
コンテスト
ユーザー paruki
提出日時 2016-05-18 20:52:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,866 bytes
コンパイル時間 2,224 ms
コンパイル使用メモリ 182,852 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-06 05:39:02
合計ジャッジ時間 2,509 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

int TT, L, A[3][3], ay, ax, by, bx;
vector<vector<pii>> pat;
vi range;

vi makeRange(){
    vi aa;
    aa.push_back(L / 2);
    if(L % 2)aa.push_back(L / 2 + 1);
    each(a, pat){
        int flag = 0;
        each(b, a){
            int y = b.first, x = b.second;
            if(y == ay&&x == ax)flag |= 1;
            if(y == by&&x == bx)flag |= 2;
        }
        each(b, a){
            int y = b.first, x = b.second;
            if((flag & 1) && A[y][x] < L)aa.push_back(A[y][x]);
            if((flag & 2) && L - A[y][x] >= 0)aa.push_back(L - A[y][x]);
        }
    }
    aa.push_back(L);
    sort(all(aa));
    aa.erase(unique(all(aa)), aa.end());
    return aa;
}

bool kado(int a, int b, int c){
    return a != b&&b != c&&c != a && ((a<b&&b>c) || (a>b&&b < c));
}

bool check(){
    int vals[3];
    each(d, pat){
        rep(i, 3)vals[i] = A[d[i].first][d[i].second];
        if(!kado(vals[0], vals[1], vals[2]))return 0;
    }
    return 1;
}

void solve(){
    ay = ax = by = bx = -1;
    rep(y, 3)rep(x, 3){
        if(A[y][x] == 0){
            if(ay == -1){
                ay = y;
                ax = x;
            } else{
                by = y;
                bx = x;
            }
        }
    }
    range = makeRange();

    ll ans = 0;
    rep(i, sz(range)-1){
        int l = range[i], r = range[i + 1];
        int len = r - l - 1;
        if(len <= 0)continue;
        int x = l + 1;
        A[ay][ax] = x;
        A[by][bx] = L - x;
        if(check()){
            ans += len;
            FOR(j, l + 1, r){
                A[ay][ax] = j;
                A[by][bx] = L - j;
            }
        }
    }

    A[ay][ax] = L / 2;
    A[by][bx] = L - L / 2;
    if(check())++ans;
    
    if(L % 2){
        A[ay][ax] = L / 2 + 1;
        A[by][bx] = L / 2;
        if(check())++ans;
    }

    cout << ans << endl;
}

void init(){
    vector<pii> c(3), d(3);
    rep(i, 3){
        vector<pii> a(3), b(3);
        rep(j, 3){
            a[j] = {i,j};
            b[j] = {j,i};
        }
        pat.push_back(a);
        pat.push_back(b);
        c[i] = {i,i};
        d[i] = {i,2 - i};
    }
    pat.push_back(c);
    pat.push_back(d);
}

int main(){
    init();
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> TT;
    while(TT--){
        cin >> L;
        rep(i, 3)rep(j, 3)cin >> A[i][j];
        solve();
    }
}
0