結果

問題 No.359 門松行列
コンテスト
ユーザー koyumeishi
提出日時 2016-01-12 04:16:46
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 3,177 bytes
コンパイル時間 761 ms
コンパイル使用メモリ 86,300 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-19 18:48:51
合計ジャッジ時間 1,637 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <cassert>
using namespace std;

template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}
template<class T> istream& operator , (istream& is, T& val){ return is >> val;}
template<class T> ostream& operator << (ostream& os, vector<T>& vec){for(int i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"\n":" ");return os;}

bool is_kadomatsu_sequence(vector<int> x){
	if(x.size() != 3) return false;
	if(x[0] < x[1] && x[1] > x[2] && x[2] != x[0]) return true;
	if(x[0] > x[1] && x[1] < x[2] && x[2] != x[0]) return true;
	return false;
}

bool is_kadomatsu_matrix(vector<int>& mat){
	for(int i=0; i<3; i++){
		if(!is_kadomatsu_sequence({mat[3*i+0], mat[3*i+1], mat[3*i+2]})) return false;
		if(!is_kadomatsu_sequence({mat[3*0+i], mat[3*1+i], mat[3*2+i]})) return false;
	}
	if(!is_kadomatsu_sequence({mat[3*0+0], mat[3*1+1], mat[3*2+2]})) return false;
	if(!is_kadomatsu_sequence({mat[3*0+2], mat[3*1+1], mat[3*2+0]})) return false;
	return true;
}

int naive(int L, vector<int> arr){
	vector<int> x;
	for(int i=0; i<9; i++){
		if(arr[i] == 0) x.push_back(i);
	}

	int ans = 0;
	for(int k=1; k<L; k++){
		arr[x[0]] = k;
		arr[x[1]] = L-k;
		if(is_kadomatsu_matrix(arr)){
			ans++;
		}
	}
	//cout << ans << endl;
	return ans;
}

int solver(int L, vector<int> arr){
	assert(1<= L && L<=1000000000);

	vector<int> x;
	for(int i=0; i<9; i++){
		if(arr[i] == 0) x.push_back(i);

		assert(0<= arr[i] && arr[i]<=1000000000);
	}

	assert(x.size() == 2);

	set<int> y;
	y.insert(0);
	y.insert(1);
	y.insert(L-1);
	y.insert(L);

	for(int i=0; i<9; i++){
		if(arr[i] == 0) continue;
		y.insert(arr[i]-1);
		y.insert(arr[i]);
		y.insert(arr[i]+1);

		y.insert(L-arr[i]-1);
		y.insert(L-arr[i]);
		y.insert(L-arr[i]+1);
	}

	y.insert(L/2-1);
	y.insert(L/2);
	y.insert(L/2+1);

	long long ans = 0;

	int last = 0;
	bool valid = false;
	for(int u : y){
		if(u<=0 || u>=L) continue;
		int v = L - u;
		
		arr[ x[0] ] = u;
		arr[ x[1] ] = v;

		bool is_km = is_kadomatsu_matrix(arr);
		if(is_km){
			if(valid == false){
				ans++;
			}else{
				ans += u-last;
			}
			last = u;
			valid = true;
		}else{
			valid = false;
		}
	}

	//cout << ans << endl;
	return ans;
}

int main(){
	int t;
	cin >> t;
	assert(1<=t && t<=100);
	while(t--){
		int L;
		vector<int> arr(9);

		cin >> L, arr;

		auto ans = solver(L, arr);

		cout << ans << endl;
	}
	return 0;
}

#include <ctime>

/*
int main_(){
	mt19937 mt((unsigned)time(NULL));
	uniform_int_distribution<int> dstr(10, 20);
	uniform_int_distribution<int> L_dstr(1, 40);

	vector<int> arr(9);
	vector<int> hoge(9);
	iota(hoge.begin(), hoge.end(), 0);

	for(int t=0; t<100000; t++){
		int L = L_dstr(mt);
		shuffle(hoge.begin(), hoge.end(), mt);

		while(1){
			for(int i=0; i<9; i++){
				arr[i] = dstr(mt);
			}
			if(is_kadomatsu_matrix(arr)) break;
		}
		arr[hoge[0]] = arr[hoge[1]] = 0;

		if( naive(L,arr) !=  solver(L,arr) ){
			cout << L << endl;
			cout << arr;
			abort();
		}
	}
	return 0;
}
*/
0