結果

問題 No.359 門松行列
ユーザー kmjpkmjp
提出日時 2016-04-17 23:56:47
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 2,881 bytes
コンパイル時間 1,765 ms
コンパイル使用メモリ 172,012 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-10-04 11:08:34
合計ジャッジ時間 6,647 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int T;
int L;
int A[9];
vector<pair<int,int>> range[9];

int li[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},
};


int isok() {
	int i;
	FOR(i,8) {
		if(A[li[i][0]]==A[li[i][1]]) return 0;
		if(A[li[i][0]]==A[li[i][2]]) return 0;
		if(A[li[i][1]]==A[li[i][2]]) return 0;
		if(A[li[i][0]]<A[li[i][1]] && A[li[i][1]]<A[li[i][2]]) return 0;
		if(A[li[i][0]]>A[li[i][1]] && A[li[i][1]]>A[li[i][2]]) return 0;
	}
	return 1;
}

vector<pair<int,int>> intersect(vector<pair<int,int>> a,vector<pair<int,int>> b) {
	vector<pair<int,int>> v;
	FORR(x,a) FORR(y,b) {
		if(x.second < x.first) continue;
		if(y.second < y.first) continue;
		if(x.second < y.first) continue;
		if(y.second < x.first) continue;
		v.push_back({max(x.first,y.first),min(x.second,y.second)});
	}
	sort(ALL(v));
	v.erase(unique(ALL(v)),v.end());
	return v;
}
vector<pair<int,int>> getrev(vector<pair<int,int>> a) {
	vector<pair<int,int>> v;
	FORR(x,a) v.push_back({L-x.second,L-x.first});
	sort(ALL(v));
	return v;
}

int dodo(int a,int b,int c) {
	int n0=(A[a]==0)+(A[b]==0)+(A[c]==0);
	vector<pair<int,int>> E;
	if(n0==0) {
		if(A[a]==A[c]) return 0;
		if(max(A[a],A[c])<A[b] || min(A[a],A[c])>A[b]) return 1;
		return 0;
	}
	else if(n0==1 && A[b]==0) {
		E.push_back({1,min(A[a],A[c])-1});
		E.push_back({max(A[a],A[c])+1,L-1});
		range[b]=intersect(range[b],E);
	}
	else if(n0==1) {
		if(A[c]==0) swap(a,c);
		if(A[b]==A[c]) return 0;
		if(A[b]>A[c]) {
			E.push_back({1,A[c]-1});
			E.push_back({A[c]+1,A[b]-1});
		}
		if(A[b]<A[c]) {
			E.push_back({A[c]-1,L-1});
			E.push_back({A[b]+1,A[c]-1});
		}
		range[b]=intersect(range[b],E);
	}
	return 1;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>L;
		vector<int> V;
		FOR(i,9) {
			cin>>A[i];
			if(A[i]==0) {
				range[i].clear();
				range[i].push_back({1,L-1});
				V.push_back(i);
			}
		}
		
		int ok=1;
		FOR(i,8) ok &= dodo(li[i][0],li[i][1],li[i][2]);
		if(ok==0) {
			_P("0\n");
			continue;
		}
		
		range[V[1]]=getrev(range[V[1]]);
		auto VV=intersect(range[V[0]],range[V[1]]);
		ll tot=0;
		FORR(r,VV) {
			for(i=r.first;i<=r.second;i++) {
				A[V[0]]=i;
				A[V[1]]=L-i;
				tot+=isok();
			}
		}
		
		_P("%lld\n",tot);
	}
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}
0