結果

問題 No.359 門松行列
ユーザー btkbtk
提出日時 2016-05-25 19:26:35
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 1,831 bytes
コンパイル時間 2,080 ms
コンパイル使用メモリ 176,000 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-19 12:48:38
合計ジャッジ時間 2,697 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

/*
* Problem link
* http://yukicoder.me/problems/940
*/

#include<bits/stdc++.h>
using namespace std;

struct INIT{INIT(){cin.tie(0);ios_base::sync_with_stdio(false);} }init;

const int checklist[8][3] = { {0,1,2} ,{ 3,4,5 },{ 6,7,8 } ,{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6} };
typedef long long LL;
typedef pair<LL, LL> P;
#define rep(i,n) for(auto i=(n)*0;i<n;i++)
#define range(it,v) for(auto &it:v)
bool checkKadomatsu(LL a, LL b, LL c) {
	return a != c && ((a<b&&b>c) || (a > b&&b < c));
}

bool checkAllKadomatsu(vector<LL> a) {
	rep(i, 8)if (!checkKadomatsu(a[checklist[i][0]], a[checklist[i][1]], a[checklist[i][2]]))return false;
	return true;
}


int main() {
#ifdef INPUT_FROM_FILE
	ifstream cin("sample.in");
	ofstream cout("sample.out");
#endif
	int T;
	while(cin >> T)
	while (T--) {
		LL L;
		vector<LL> a(9);
		cin >> L; rep(i, 9)cin >> a[i];
		set<LL> wall;
		wall.insert(1);
		wall.insert(L);
		vector<int> pos;
		rep(i, 9) {
			if (a[i]== 0)pos.push_back(i);
			else if (a[i] < L) {
				wall.insert(a[i]);
				wall.insert(L-a[i]);
				if (a[i] < L - 1) {
					wall.insert(a[i] + 1);
					wall.insert(L - a[i] - 1);
				}
				if (a[i] > 1) {
					wall.insert(a[i] - 1);
					wall.insert(L - a[i] + 1);
				}
			}
		}
		vector<LL> seg;
		range(it, wall)seg.push_back(it);
		int m = seg.size(); m--;
		rep(i, m) {
			LL t = (seg[i] + seg[i + 1]) / 2;
			wall.insert(t);
			wall.insert(L - t);
			if (t < L - 1) {
				wall.insert(t + 1);
				wall.insert(L - t - 1);
			}
			if (t > 1) {
				wall.insert(t - 1);
				wall.insert(L - t + 1);
			}
		}
		seg.clear();
		range(it, wall)seg.push_back(it);
		m = seg.size(); m--;
		LL res = 0;
		rep(i, m) {
			a[pos[0]] = seg[i];
			a[pos[1]] = L - seg[i];
			if (checkAllKadomatsu(a)) {
				res += (seg[i + 1] - seg[i]);
			}
		}
		cout << res << endl;
	}
	
	return 0;
}
0