結果
| 問題 |
No.359 門松行列
|
| コンテスト | |
| ユーザー |
 omu
|
| 提出日時 | 2016-04-18 02:51:16 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 7,943 bytes |
| コンパイル時間 | 1,586 ms |
| コンパイル使用メモリ | 121,768 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2024-10-04 13:02:14 |
| 合計ジャッジ時間 | 3,473 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | RE * 17 |
コンパイルメッセージ
main.cpp: In lambda function:
main.cpp:286:17: warning: control reaches end of non-void function [-Wreturn-type]
286 | }();
| ^
ソースコード
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <list>
#include <tuple>
#include <bitset>
#include <ciso646>
#include <cassert>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
typedef vector<ll> vec;
inline bool check(ll x, ll y, ll xMax, ll yMax) { return x >= 0 && y >= 0 && xMax > x && yMax > y; }
inline int toint(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string tostring(T x) { ostringstream sout; sout << x; return sout.str(); }
template<class T> inline T sqr(T x) { return x*x; }
template<class T> inline T mypow(T x, ll n) { T res = 1; while (n > 0) { if (n & 1)res = res * x; x = x * x; n >>= 1; }return res; }
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
#define For(i,a,b) for(ll (i) = (a);i < (b);(i)++)
#define rep(i,n) For(i,0,n)
#define rFor(i,a,b) for(ll (i) = (a-1);i >= (b);(i)--)
#define rrep(i,n) rFor(i,n,0)
#define each(i,n) for(auto &i : n)
#define clr(a) memset((a), 0 ,sizeof(a))
#define mclr(a) memset((a), -1 ,sizeof(a))
#define all(a) (a).begin(),(a).end()
#define sz(a) (sizeof(a))
#define tostr(a) tostring(a)
#define dump(val) cerr << #val " = " << val << endl;
#define Fill(a,v) fill((int*)a,(int*)(a+(sz(a)/sz(*(a)))),v)
const ll dx[8] = { 1, 0, -1, 0, 1, 1, -1, -1 }, dy[8] = { 0, -1, 0, 1, -1, 1, -1, 1 };
const ll mod = 1e9 + 7;
const ll INF = 1e17 + 9;
#define int ll
#define double ld
struct Point {
int x, y;
Point() { x = -1, y = -1; }
Point(int x, int y)
: x(x)
, y(y)
{}
bool operator < (Point &other) {
return x < other.x || (x == other.x && y < other.y);
}
bool operator == (Point &other) {
return (x == other.x && y == other.y);
}
};
typedef tuple<Point, Point, Point> P3;
bool isKadoMatuRetu(int t1, int t2, int t3) {
if (t1 == t2 || t2 == t3 || t3 == t1)return false;
return (t2 == min({ t1,t2,t3 }) || t2 == max({ t1,t2,t3 }));
}
vector<P3> judgeTarget;
vector<bool> kind(8, true);
void init() {
for (int r = 0; r < 3; r++) {
judgeTarget.push_back(make_tuple(Point(r, 0), Point(r, 1), Point(r, 2)));
}
for (int c = 0; c < 3; c++) {
judgeTarget.push_back(make_tuple(Point(0, c), Point(1, c), Point(2, c)));
}
judgeTarget.push_back(make_tuple(Point(0, 2), Point(1, 1), Point(2, 0)));
judgeTarget.push_back(make_tuple(Point(0, 0), Point(1, 1), Point(2, 2)));
}
bool isKadoMatuRetu3D(vector<vector<int>> t) {
if (t.size() != 3 || t[0].size() != 3)return false;
for (auto i : judgeTarget) {
int x0 = get<0>(i).x, y0 = get<0>(i).y,
x1 = get<1>(i).x, y1 = get<1>(i).y,
x2 = get<2>(i).x, y2 = get<2>(i).y;
if (!t[x0][y0] || !t[x1][y1] || !t[x2][y2])continue;
if (isKadoMatuRetu(t[x0][y0], t[x1][y1], t[x2][y2]) == false) {
return false;
}
}
return true;
}
signed main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
init();
int T;
cin >> T;
for (int _ = 0; _ < T; _++) {
[]() {
int L;
cin >> L;
vector<vector<int>> a(3, vector<int>(3));
vector<Point> zero;
rep(i, 3)rep(j, 3) {
cin >> a[i][j];
if (a[i][j] == 0) {
zero.push_back(Point(i, j));
}
}
int zx0 = zero[0].x, zy0 = zero[0].y,
zx1 = zero[1].x, zy1 = zero[1].y;
set<int> NG[3][3];
bool ok = true;
bool near = false;
for (auto i : judgeTarget) {
int x0 = get<0>(i).x, y0 = get<0>(i).y,
x1 = get<1>(i).x, y1 = get<1>(i).y,
x2 = get<2>(i).x, y2 = get<2>(i).y;
int t0 = a[x0][y0], t1 = a[x1][y1], t2 = a[x2][y2];
if (t0 && t0 == t1)ok = false;
if (t1 && t1 == t2)ok = false;
if (t2 && t2 == t0)ok = false;
NG[x0][y0].insert(t1);
NG[x0][y0].insert(t2);
NG[x1][y1].insert(t0);
NG[x1][y1].insert(t2);
NG[x2][y2].insert(t1);
NG[x2][y2].insert(t0);
int cnt = (t0 == 0 ? 1 : 0) + (t1 == 0 ? 1 : 0) + (t2 == 0 ? 1 : 0);
if (cnt == 2) {
near = true;
}
}
if (!ok || isKadoMatuRetu3D(a) == false) {
cout << 0 << endl;
return 0;
}
function<int(int)> dfs = [&](int m) {
int count = 0;
if (m == 8) {
int maxTable[3][3], minTable[3][3];
Fill(maxTable, L - 1);
Fill(minTable, 1);
rep(x, 3)rep(y, 3) {
if (a[x][y] != 0) {
maxTable[x][y] = a[x][y];
minTable[x][y] = a[x][y];
}
}
//a[zx0][zy0] < a[zx1][zy1]かどうか
bool large_0_1 = false;
//a[zx0][zy0] > a[zx1][zy1]かどうか
bool small_0_1 = false;
rep(__, 3)
rep(i, judgeTarget.size()) {
auto target = judgeTarget[i];
int x0 = get<0>(target).x, y0 = get<0>(target).y,
x1 = get<1>(target).x, y1 = get<1>(target).y,
x2 = get<2>(target).x, y2 = get<2>(target).y;
auto ma0 = &maxTable[x0][y0],
ma1 = &maxTable[x1][y1],
ma2 = &maxTable[x2][y2],
mi0 = &minTable[x0][y0],
mi1 = &minTable[x1][y1],
mi2 = &minTable[x2][y2];
if (kind[i]) { //t1が一番大きい
(*ma0) = min((*ma1) - 1, (*ma0));
(*ma2) = min((*ma1) - 1, (*ma2));
(*mi1) = max((*mi0) + 1, (*mi1));
(*mi1) = max((*mi2) + 1, (*mi1));
if ( ma1 == &maxTable[zx0][zy0] &&
(ma0 == &maxTable[zx1][zy1] || ma2 == &maxTable[zx1][zy1])) {
small_0_1 = true;
}
if ( ma1 == &maxTable[zx1][zy1] &&
(ma0 == &maxTable[zx0][zy0] || ma2 == &maxTable[zx0][zy0])) {
large_0_1 = true;
}
}
else { //t1が一番小さい
(*mi0) = max((*mi1) + 1, (*mi0));
(*mi2) = max((*mi1) + 1, (*mi2));
(*ma1) = min((*ma0) - 1, (*ma1));
(*ma1) = min((*ma2) - 1, (*ma1));
if ( mi1 == &maxTable[zx0][zy0] &&
(mi0 == &maxTable[zx1][zy1] || mi2 == &maxTable[zx1][zy1])) {
large_0_1 = true;
}
if ( mi1 == &maxTable[zx1][zy1] &&
(mi0 == &maxTable[zx0][zy0] || mi2 == &maxTable[zx0][zy0])) {
small_0_1 = true;
}
}
}
rep(__, 3) {
if (large_0_1) {
minTable[zx1][zy1] = max(minTable[zx1][zy1], L - maxTable[zx0][zy0] + 1);
maxTable[zx0][zy0] = min(minTable[zx0][zy0], L - minTable[zx1][zy1] - 1);
}
if (small_0_1) {
minTable[zx0][zy0] = max(minTable[zx0][zy0], L - maxTable[zx1][zy1] + 1);
maxTable[zx1][zy1] = min(minTable[zx1][zy1], L - minTable[zx0][zy0] - 1);
}
}
rep(__, 3) {
maxTable[zx1][zy1] = min(maxTable[zx1][zy1], L - minTable[zx0][zy0]);
minTable[zx1][zy1] = max(minTable[zx1][zy1], L - maxTable[zx0][zy0]);
maxTable[zx0][zy0] = min(maxTable[zx0][zy0], L - minTable[zx1][zy1]);
minTable[zx0][zy0] = max(minTable[zx0][zy0], L - maxTable[zx1][zy1]);
}
rep(x, 3)rep(y, 3) {
if (minTable[x][y] > maxTable[x][y]) {
return 0ll;
}
}
int ma0 = maxTable[zx0][zy0], mi0 = minTable[zx0][zy0],
ma1 = maxTable[zx1][zy1], mi1 = minTable[zx1][zy1];
int minus = 0;
set<int> tmp;
for (auto ng : NG[zx0][zy0]) {
if (mi0 <= ng && ng <= ma0) {
minus++;
tmp.insert(L - ng);
}
}
for (auto ng : NG[zx1][zy1]) {
if (tmp.count(ng) == 0 && mi1 <= ng && ng <= ma1) {
minus++;
}
}
count = min((ma0 - mi0 + 1ll), (ma1 - mi1 + 1ll));
if (near && L%2 == 0 && mi0 <= L/2 && L/2 <= ma0 && mi1 <= L/2 && L/2 <= ma1) {
count--;
}
count -= minus;
if (count < 0)count = 0ll;
return count;
}
kind[m] = true; count += dfs(m + 1);
kind[m] = false; count += dfs(m + 1);
return count;
};
int ans = dfs(0);
cout << ans << endl;
}();
}
return 0;
}