結果
| 問題 | No.359 門松行列 |
| ユーザー |
 h_noson
|
| 提出日時 | 2016-04-18 02:29:38 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 17 |
ソースコード
#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 100000000typedef 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++;elseib++;}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)));}elseret.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));}elseret.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;elsereturn 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]));elserange = 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]));elserange = 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]));elserange = 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]));elserange = 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;}