Submission #434476
Source Code Expand
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
class Myon
{
public Myon() { }
public static int Main()
{
new Myon().calc();
return 0;
}
Scanner cin;
List<int> pos = new List<int>();
List<int> num = new List<int>();
int[] posrev;
int N = 5;
int[,] board;
void calc()
{
cin = new Scanner();
board = new int[N, N];
posrev = new int[N * N];
for (int i = 0; i < posrev.Length; i++)
{
posrev[i] = -1;
}
for (int i = 0; i < 25; i++)
{
num.Add(i);
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
board[i, j] = cin.nextInt() - 1;
if (board[i, j] == -1)
{
int num = i * 5 + j;
posrev[num] = pos.Count;
pos.Add(num);
}
else
{
num.Remove(board[i, j]);
}
}
}
long[] dp = new long[1 << pos.Count];
dp[0] = 1;
long mod = 1000000007;
for (int i = 0; i < (1 << pos.Count) - 1; i++)
{
int count = bitCount(i);
int nownumber = num[count];
bool[,] used = new bool[N, N];
bool flag2 = true;
for (int j = 0; j < posrev.Length; j++)
{
int y = j / 5;
int x = j % 5;
if (posrev[j] == -1)
{
if (board[y, x] < nownumber)
{
used[y, x] = true;
int prenumber = -1;
if (count != 0) prenumber = num[count - 1];
if (prenumber > board[y, x])
{
if (y != 0 && y != 4)
{
int up = board[y + 1, x];
int down = board[y - 1, x];
if (up == -1)
{
int p = posrev[(y + 1) * 5 + (x)];
if ((i >> p) % 2 == 1) up = prenumber;
else up = nownumber;
}
if (down == -1)
{
int p = posrev[(y - 1) * 5 + (x)];
if ((i >> p) % 2 == 1) down = prenumber;
else down = nownumber;
}
if ((up > board[y, x]) != (down > board[y, x]))
{
flag2 = false;
break;
}
}
if (x != 0 && x != 4)
{
int up = board[y, x + 1];
int down = board[y, x - 1];
if (up == -1)
{
int p = posrev[(y) * 5 + (x + 1)];
if ((i >> p) % 2 == 1) up = prenumber;
else up = nownumber;
}
if (down == -1)
{
int p = posrev[(y) * 5 + (x - 1)];
if ((i >> p) % 2 == 1) down = prenumber;
else down = nownumber;
}
if ((up > board[y, x]) != (down > board[y, x]))
{
flag2 = false;
break;
}
}
}
}
}
else
{
if ((i >> posrev[j]) % 2 == 1)
{
used[y, x] = true;
}
}
}
if (!flag2) continue;
for (int j = 0; j < pos.Count; j++)
{
if ((i >> j) % 2 == 1) continue;
int y = pos[j] / 5;
int x = pos[j] % 5;
bool flag = true;
if (y != 0 && y != 4)
{
if (used[y + 1, x] != used[y - 1, x])
{
flag = false;
break;
}
}
if (x != 0 && x != 4)
{
if (used[y, x + 1] != used[y, x - 1])
{
flag = false;
break;
}
}
if (flag)
{
dp[i | (1 << j)] += dp[i];
dp[i | (1 << j)] %= mod;
}
}
}
Console.WriteLine(dp[(1 << pos.Count) - 1]);
}
int bitCount(long x)
{
x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555);
x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);
x = (x & 0x0f0f0f0f0f0f0f0f) + (x >> 4 & 0x0f0f0f0f0f0f0f0f);
x = (x & 0x00ff00ff00ff00ff) + (x >> 8 & 0x00ff00ff00ff00ff);
x = (x & 0x0000ffff0000ffff) + (x >> 16 & 0x0000ffff0000ffff);
return (int)((x & 0x00000000ffffffff) + (x >> 32 & 0x00000000ffffffff));
}
}
class Scanner
{
string[] s;
int i;
char[] cs = new char[] { ' ' };
public Scanner()
{
s = new string[0];
i = 0;
}
public string next()
{
if (i < s.Length) return s[i++];
string st = Console.ReadLine();
while (st == "") st = Console.ReadLine();
s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
i = 0;
return next();
}
public int nextInt()
{
return int.Parse(next());
}
public long nextLong()
{
return long.Parse(next());
}
public double nextDouble()
{
return double.Parse(next());
}
}
Submission Info
Submission Time |
|
Task |
D - 25個の整数 |
User |
chokudai |
Language |
C# (Mono 3.2.1.0) |
Score |
0 |
Code Size |
6790 Byte |
Status |
WA |
Exec Time |
1249 ms |
Memory |
21076 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
0 / 30 |
0 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt |
Subtask1 |
sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, test-1-01.txt, test-1-02.txt, test-1-03.txt, test-1-04.txt, test-1-05.txt, test-1-06.txt, test-1-07.txt, test-1-08.txt, test-1-09.txt, test-1-10.txt, test-1-11.txt, test-1-12.txt, test-1-13.txt, test-1-14.txt, test-1-15.txt |
Subtask2 |
sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, test-1-01.txt, test-1-02.txt, test-1-03.txt, test-1-04.txt, test-1-05.txt, test-1-06.txt, test-1-07.txt, test-1-08.txt, test-1-09.txt, test-1-10.txt, test-1-11.txt, test-1-12.txt, test-1-13.txt, test-1-14.txt, test-1-15.txt, test-2-01.txt, test-2-02.txt, test-2-03.txt, test-2-04.txt, test-2-05.txt, test-2-06.txt, test-2-07.txt, test-2-08.txt, test-2-09.txt, test-2-10.txt |
Case Name |
Status |
Exec Time |
Memory |
sample-01.txt |
WA |
114 ms |
8960 KB |
sample-02.txt |
AC |
112 ms |
8988 KB |
sample-03.txt |
AC |
111 ms |
8944 KB |
sample-04.txt |
AC |
113 ms |
8960 KB |
test-1-01.txt |
AC |
114 ms |
8988 KB |
test-1-02.txt |
WA |
112 ms |
8964 KB |
test-1-03.txt |
WA |
112 ms |
9000 KB |
test-1-04.txt |
WA |
113 ms |
8964 KB |
test-1-05.txt |
WA |
116 ms |
8964 KB |
test-1-06.txt |
WA |
113 ms |
8952 KB |
test-1-07.txt |
AC |
113 ms |
8988 KB |
test-1-08.txt |
WA |
113 ms |
8984 KB |
test-1-09.txt |
WA |
114 ms |
8984 KB |
test-1-10.txt |
AC |
113 ms |
8964 KB |
test-1-11.txt |
AC |
112 ms |
8904 KB |
test-1-12.txt |
WA |
113 ms |
8944 KB |
test-1-13.txt |
AC |
113 ms |
8988 KB |
test-1-14.txt |
WA |
113 ms |
8988 KB |
test-1-15.txt |
WA |
112 ms |
8964 KB |
test-2-01.txt |
WA |
154 ms |
11576 KB |
test-2-02.txt |
WA |
123 ms |
9636 KB |
test-2-03.txt |
WA |
118 ms |
9292 KB |
test-2-04.txt |
WA |
177 ms |
13452 KB |
test-2-05.txt |
WA |
251 ms |
13916 KB |
test-2-06.txt |
WA |
1073 ms |
21072 KB |
test-2-07.txt |
WA |
1219 ms |
21076 KB |
test-2-08.txt |
WA |
1249 ms |
21048 KB |
test-2-09.txt |
WA |
1216 ms |
21048 KB |
test-2-10.txt |
WA |
1132 ms |
21068 KB |