Submission #1872606
Source Code Expand
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
using namespace std;
#define INF 0x3f3f3f3f
//#define INF 1100000000000000000LL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=100050;
//ここまでテンプレ
//↓整数をpopcount orderで生成するセット
int next_perm(int v){
//
if(v==0)
return (1<<30)-1;
//v=0を入れると0除算が発生して停止するので注意!!
int t=(v|(v-1))+1;
int w=t|((((t&(-t))/(v&(-v)))>>1)-1);
return w;
}
int element_0(int c){
return (1<<c)-1;
}
//↑整数をpopcount orderで生成するセット
vint tate[26],yoko[26];
bool hantei(int v,int i){
char a=0,b=0;
//たての判定
for(int j:tate[i]){
if(v&(1<<j))
a++;
}
//よこの判定
for(int j:yoko[i]){
if(v&(1<<j))
b++;
}
if(a==1 || b==1)
return 0;
else
return 1;
}
int main() {
//00~24の25マスについて
int a[2]={-5,5};
int b[2]={-1,1};
//縦につながっているマスどうしのpathを記録
for(int i=0;i<25;i++){
for(int j=0;j<2;j++){
if(i+a[j]<0 || 24<i+a[j])
continue;
tate[i].pb(i+a[j]);
}
}
//横につながっているマスどうしのpathを記録
for(int i=0;i<25;i++){
for(int j=0;j<2;j++){
if(j==0 && i%5==0)
continue;
if(j==1 && i%5==4)
continue;
yoko[i].pb(i+b[j]);
}
}
//場所が決まっている数字
//must[数字]=場所
int must[26]={};
for(int i=0;i<25;i++){
must[i]=-1;
int c;
cin>>c;
if(c==0)
continue;
must[i]=c-1;
}
//DPテーブル
int DP[2<<25]={};
DP[0]=1;
//popcount orderでDPテーブルをまわす
for(int i=0;i<25;i++){
//popしているbitの数がiである整数をまわす
int v=element_0(i);
while(1){
//iを置く場所が決まっているとき、そこにおけるかどうかだけ見る
if(must[i]!=-1){
if(v&(1<<must[i]))
continue;
if(hantei(v,must[i])){
DP[v+(1<<must[i])]+=DP[v];
}
}
for(int j=0;j<25;j++){
if(v&(1<<j))
continue;
if(hantei(v,j)){
DP[v+(1<<j)]+=DP[v];
DP[v+(1<<j)]%=MOD;
}
}
v=next_perm(v);
//25bit目が立っている数が現れたら止める
if(v&(1<<25))
break;
}
}
cout<<DP[1<<25-1]<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 25個の整数 |
User |
takeo1116 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2922 Byte |
Status |
RE |
Exec Time |
100 ms |
Memory |
256 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 |
RE |
97 ms |
256 KB |
sample-02.txt |
RE |
97 ms |
256 KB |
sample-03.txt |
RE |
97 ms |
256 KB |
sample-04.txt |
RE |
97 ms |
256 KB |
test-1-01.txt |
RE |
97 ms |
256 KB |
test-1-02.txt |
RE |
97 ms |
256 KB |
test-1-03.txt |
RE |
97 ms |
256 KB |
test-1-04.txt |
RE |
97 ms |
256 KB |
test-1-05.txt |
RE |
97 ms |
256 KB |
test-1-06.txt |
RE |
98 ms |
256 KB |
test-1-07.txt |
RE |
98 ms |
256 KB |
test-1-08.txt |
RE |
97 ms |
256 KB |
test-1-09.txt |
RE |
97 ms |
256 KB |
test-1-10.txt |
RE |
97 ms |
256 KB |
test-1-11.txt |
RE |
97 ms |
256 KB |
test-1-12.txt |
RE |
97 ms |
256 KB |
test-1-13.txt |
RE |
97 ms |
256 KB |
test-1-14.txt |
RE |
99 ms |
256 KB |
test-1-15.txt |
RE |
97 ms |
256 KB |
test-2-01.txt |
RE |
97 ms |
256 KB |
test-2-02.txt |
RE |
97 ms |
256 KB |
test-2-03.txt |
RE |
97 ms |
256 KB |
test-2-04.txt |
RE |
98 ms |
256 KB |
test-2-05.txt |
RE |
98 ms |
256 KB |
test-2-06.txt |
RE |
97 ms |
256 KB |
test-2-07.txt |
RE |
100 ms |
256 KB |
test-2-08.txt |
RE |
100 ms |
256 KB |
test-2-09.txt |
RE |
97 ms |
256 KB |
test-2-10.txt |
RE |
97 ms |
256 KB |