結果

問題 No.359 門松行列
コンテスト
ユーザー paruki
提出日時 2016-05-18 21:12:12
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,341 bytes
コンパイル時間 1,921 ms
コンパイル使用メモリ 181,760 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-11 01:02:17
合計ジャッジ時間 2,673 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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{0,L,L / 2,L / 2 + 1};
    rep(y, 3)rep(x, 3){
        if(A[y][x]){
            if(L - A[y][x] > 0)aa.push_back(L - A[y][x]);
            if(A[y][x] < L)aa.push_back(A[y][x]);
        } else{
            if(ay == -1){
                ay = y;
                ax = x;
            } else{
                by = y;
                bx = x;
            }
        }
    }
    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;
    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(i, 1, sz(range) - 1){
        int x = range[i];
        A[ay][ax] = x;
        A[by][bx] = L - x;
        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