結果

問題 No.359 門松行列
コンテスト
ユーザー mayoko_
提出日時 2016-04-22 19:37:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 3,081 bytes
コンパイル時間 1,189 ms
コンパイル使用メモリ 114,132 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-11 00:00:47
合計ジャッジ時間 1,890 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
#include<complex>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>
#include<random>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

bool isKadomatsu(int a0, int a1, int a2) {
    if (a0 == a1 || a0 == a2 || a1 == a2) return false;
    if (a0 > a1 && a1 < a2) return true;
    if (a0 < a1 && a1 > a2) return true;
    return false;
}

int A[3][3];

bool isOK() {
    for (int i = 0; i < 3; i++) {
        if (!isKadomatsu(A[i][0], A[i][1], A[i][2])) return false;
        if (!isKadomatsu(A[0][i], A[1][i], A[2][i])) return false;
    }
    if (!isKadomatsu(A[0][0], A[1][1], A[2][2])) return false;
    if (!isKadomatsu(A[0][2], A[1][1], A[2][0])) return false;
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int L;
        cin >> L;
        vi empty;
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) {
            cin >> A[i][j];
            if (A[i][j] == 0) empty.push_back(i*3+j);
        }
        vi vs;
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) {
            if (A[i][j] != 0) {
                if (L-A[i][j] > 0) {
                    vs.push_back(A[i][j]);
                    vs.push_back(L-A[i][j]);
                }
            }
        }
        for (int i = -1; i <= 1; i++) {
            if (L/2+i > 0) vs.push_back(L/2+i);
        }
        vs.push_back(L/2);
        sort(vs.begin(), vs.end());
        vs.erase(unique(vs.begin(), vs.end()), vs.end());
        vector<pii> ps;
        int n = vs.size();
        if (vs[0] > 1) ps.emplace_back(1, vs[0]-1);
        for (int i = 0; i < n; i++) {
            ps.emplace_back(vs[i], vs[i]);
            if (i < n-1) {
                if (vs[i]+1 < vs[i+1]) ps.emplace_back(vs[i]+1, vs[i+1]-1);
            }
        }
        if (vs.back() < L-1) ps.emplace_back(vs.back()+1, L-1);
        int ans = 0;
        for (pii p : ps) {
//            cout << p.first << "  " << p.second ;
            A[empty[0]/3][empty[0]%3] = p.first;
            A[empty[1]/3][empty[1]%3] = L-p.first;
            if (isOK()) {
//                cout << " OK" << endl;
                ans += p.second-p.first+1;
            } //else cout << " NG" << endl;
        }
        cout << ans << endl;
//        ans = 0;
//        for (int l = 1; l < L; l++) {
//            A[empty[0]/3][empty[0]%3] = l;
//            A[empty[1]/3][empty[1]%3] = L-l;
//            if (isOK()) {
//                cout << l << "  ";
//                ans++;
//            }
//        }
//        cout << endl << ans << endl;
    }
    return 0;
}
0