Submission #434471
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; //ここの判定が嘘なのでwrong answerになる } } 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 | 4379 Byte |
Status | WA |
Exec Time | 1094 ms |
Memory | 15344 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 | AC | 94 ms | 3148 KB |
sample-02.txt | AC | 94 ms | 3176 KB |
sample-03.txt | WA | 93 ms | 3136 KB |
sample-04.txt | AC | 94 ms | 3136 KB |
test-1-01.txt | AC | 91 ms | 3164 KB |
test-1-02.txt | WA | 93 ms | 3136 KB |
test-1-03.txt | WA | 93 ms | 3172 KB |
test-1-04.txt | WA | 93 ms | 3128 KB |
test-1-05.txt | WA | 93 ms | 3168 KB |
test-1-06.txt | WA | 92 ms | 3092 KB |
test-1-07.txt | AC | 92 ms | 3136 KB |
test-1-08.txt | WA | 93 ms | 3176 KB |
test-1-09.txt | WA | 94 ms | 3172 KB |
test-1-10.txt | AC | 95 ms | 3132 KB |
test-1-11.txt | AC | 91 ms | 3128 KB |
test-1-12.txt | WA | 95 ms | 3136 KB |
test-1-13.txt | AC | 92 ms | 3136 KB |
test-1-14.txt | WA | 93 ms | 3172 KB |
test-1-15.txt | WA | 94 ms | 3128 KB |
test-2-01.txt | WA | 128 ms | 5980 KB |
test-2-02.txt | WA | 102 ms | 3824 KB |
test-2-03.txt | WA | 97 ms | 3476 KB |
test-2-04.txt | WA | 163 ms | 7736 KB |
test-2-05.txt | WA | 223 ms | 8212 KB |
test-2-06.txt | WA | 1073 ms | 15344 KB |
test-2-07.txt | WA | 1050 ms | 15324 KB |
test-2-08.txt | WA | 1094 ms | 15328 KB |
test-2-09.txt | WA | 1087 ms | 15324 KB |
test-2-10.txt | WA | 1065 ms | 15328 KB |