結果

問題 No.359 門松行列
ユーザー h_nosonh_noson
提出日時 2016-04-18 02:29:38
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 5,957 bytes
コンパイル時間 644 ms
コンパイル使用メモリ 72,356 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-04 12:57:01
合計ジャッジ時間 1,246 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP(i,n,0)
#define REP(i,s,e) for (i = s; i < e; i++)
#define rep(i,n) REP(i,0,n)
#define INF 100000000

typedef long long ll;

vector<pair<int,int>> integrate(vector<pair<int,int>> a, vector<pair<int,int>> b) {
    vector<pair<int,int>> ret;
    int ia, ib;
    ia = ib = 0;
    while (ia < a.size() && ib < b.size()) {
        if (a[ia].second < b[ib].first) {
            ia++;
            continue;
        }
        else if (b[ib].second < a[ia].first) {
            ib++;
            continue;
        }
        ret.push_back(make_pair(max(a[ia].first,b[ib].first),min(a[ia].second,b[ib].second)));
        if (a[ia].second <= b[ib].second)
            ia++;
        else
            ib++;
    }
    return ret;
}

vector<pair<int,int>> solve(int l, bool center, int a, int b) {
    vector<pair<int,int>> ret;
    if (center) {
        if (a == 0 || b == 0) {
            int x = max(a,b);
            if (l / 2 >= x) {
                ret.push_back(make_pair(1,x-1));
                if ((l+1)/2-1 > x)
                    ret.push_back(make_pair(l/2+1,l-x-1));
                ret.push_back(make_pair(l-x+1,l-1));
            }
            else {
                ret.push_back(make_pair(1,l-x-1));
                if ((l-1)/2+1 < x)
                    ret.push_back(make_pair(l-x+1,(l-1)/2));
                if (x < l-1)
                    ret.push_back(make_pair(x+1,l-1));
            }
        }
        else {
            if (min(a,b) > 1)
                ret.push_back(make_pair(1,min({a-1,b-1,l-1})));
            if (max(a,b) < l-1)
                ret.push_back(make_pair(max(a,b)+1,l-1));
        }
    }
    else {
        if (a == 0) {
            if (l / 2 >= b) {
                ret.push_back(make_pair(1,b-1));
                if ((l+1)/2-1 > b)
                    ret.push_back(make_pair(b+1,(l-1)/2));
                if (b > 1)
                    ret.push_back(make_pair(l-b+1,l-1));
            }
            else {
                if (b < l-1)
                    ret.push_back(make_pair(1,l-b-1));
                if (l/2+1 < b)
                    ret.push_back(make_pair(l/2+1,b-1));
                if (b < l-1)
                    ret.push_back(make_pair(b+1,l-1));
            }
        }
        else if (b == 0) {
            if (l/2+1 < a) {
                if (l % 2 == 0) {
                    ret.push_back(make_pair(1,l/2-1));
                    ret.push_back(make_pair(l/2+1,min(l-1,a-1)));
                }
                else
                    ret.push_back(make_pair(1,min(l-1,a-1)));
            }
            else if ((l+1)/2-1 > a) {
                if (l % 2 == 0) {
                    ret.push_back(make_pair(a+1,l/2-1));
                    ret.push_back(make_pair(l/2+1,l-a-1));
                }
                else
                    ret.push_back(make_pair(a+1,l-a-1));
            }
        }
        else {
            if (a < b) {
                if (b - a > 1 && l-1 > a)
                    ret.push_back(make_pair(a+1,min(b-1,l-1)));
                if (b < l-1)
                    ret.push_back(make_pair(b+1,l-1));
            }
            else {
                if (b > 1)
                    ret.push_back(make_pair(1,min(b-1,l-1)));
                if (a - b > 1 && l-1 > b)
                    ret.push_back(make_pair(b+1,min(a-1,l-1)));
            }
        }
    }
    return ret;
}

bool is_kadomatsu(int a, int b, int c) {
    if (a != c && (b < min(a,c) || b > max(a,c)))
        return true;
    else if (a == 0 && b != c || b == 0 && a != c || c == 0 && a != b)
        return true;
    else
        return false;
}

int main() {
    int t, k;
    cin >> t;
    rep (k,t) {
        int i, j, l, cnt, ans;
        int a[3][3];
        vector<pair<int,int>> range;
        cin >> l;
        rep (i,3) rep (j,3) cin >> a[i][j];
        bool kadomatsu = true;
        rep (i,3)
            kadomatsu &= is_kadomatsu(a[i][0],a[i][1],a[i][2]);
        rep (i,3)
            kadomatsu &= is_kadomatsu(a[0][i],a[1][i],a[2][i]);
        kadomatsu &= is_kadomatsu(a[0][0],a[1][1],a[2][2]);
        kadomatsu &= is_kadomatsu(a[0][2],a[1][1],a[2][0]);
        if (!kadomatsu) {
            cout << 0 << endl;
            continue;
        }
        range.push_back(make_pair(1,l-1));
        rep (i,3) {
            rep (j,3) {
                if (a[i][j] == 0) {
                    if (i == 1)
                        range = integrate(range,solve(l,true,a[0][j],a[2][j]));
                    else
                        range = integrate(range,solve(l,false,a[1][j],max(a[0][j],a[2][j])));
                    if (j == 1)
                        range = integrate(range,solve(l,true,a[i][0],a[i][2]));
                    else
                        range = integrate(range,solve(l,false,a[i][1],max(a[i][0],a[i][2])));
                    if (i == j) {
                        if (i == 1)
                            range = integrate(range,solve(l,true,a[0][0],a[2][2]));
                        else
                            range = integrate(range,solve(l,false,a[1][1],max(a[0][0],a[2][2])));
                    }
                    if (i == 2-j) {
                        if (i == 1)
                            range = integrate(range,solve(l,true,a[0][2],a[2][0]));
                        else
                            range = integrate(range,solve(l,false,a[1][1],max(a[0][2],a[2][0])));
                    }
                    auto tmp = range;
                    range.clear();
                    for (auto p = tmp.rbegin(); p != tmp.rend(); p++)
                        range.push_back(make_pair(l-p->second,l-p->first));
                }
            }
        }
        ans = 0;
        for (auto p : range)
            ans += p.second - p.first + 1;
        cout << ans << endl;
    }
    return 0;
}
0