Submission #3978499


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template < typename T >
void vprint(T &v){
	REP(i, v.size()){
		cout << v[i] << " ";
	}
	cout << endl;
}

ll dp[1<<25];
ll x[25], pos[25];

void print_state(ll state){
	REP(i, 5){
		REP(j, 5){
			cout << (state>>(5*i+j) & 1) << " ";
		}
		cout << endl;
	}
	return;
}

bool check(ll state, ll rc){
	int r = rc/5;
	int c = rc%5;

	bool flag1 = (r==0||r==4);
	bool flag2 = (c==0||c==4);
	bool res;

	if(flag1 && flag2){
		res = true;
	}
	if(!flag1 && flag2){
		bool ue = (state>>(rc-5) & 1);
		bool shita = (state>>(rc+5) & 1);
		res = !(ue^shita);
	}
	if(flag1 && !flag2){
		bool hidari = (state>>(rc-1) & 1);
		bool migi = (state>>(rc+1) & 1);
		res = !(hidari^migi);
	}
	if(!flag1 && !flag2){
		bool ue = (state>>(rc-5) & 1);
		bool shita = (state>>(rc+5) & 1);
		bool hidari = (state>>(rc-1) & 1);
		bool migi = (state>>(rc+1) & 1);
		res = (!(hidari^migi) && !(ue^shita));
	}
	return res;
}

ll rec(ll state, ll next){

	if(dp[state]>=0) return dp[state];
	if(next==26) return 1;
	ll res = 0;
	if(pos[next]==-1){
		REP(i, 25){
			if(state>>i & 1) continue;
			if(x[i]>0) continue;
			if(check(state, i)){
				res += rec(state + (1<<i), next+1);
				res %= mod;
			}
		}
	}else{
		if(check(state, pos[next])){
			res += rec(state + (1<<pos[next]), next+1);
			res %= mod;
		}
	}
	/*
	cout << next << endl;
	print_state(state);
	cout << res << endl;
	cout << endl;
	*/

	dp[state] = res;
	return res;
}

int main(){
	REP(i, 25) cin >> x[i];
	REP(i, 25) pos[i] = -1;
	REP(i, 25){
		if(x[i]==0) continue;
		pos[x[i]] = i;
	}

	REP(i, 1<<25) dp[i] = -1;
	ll res = rec(0, 1);
	cout << res << endl;
    return 0;
}

Submission Info

Submission Time
Task D - 25個の整数
User theory_and_me
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2139 Byte
Status MLE
Exec Time 186 ms
Memory 262400 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
MLE × 4
MLE × 19
MLE × 29
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 MLE 83 ms 262400 KB
sample-02.txt MLE 84 ms 262400 KB
sample-03.txt MLE 83 ms 262400 KB
sample-04.txt MLE 84 ms 262400 KB
test-1-01.txt MLE 84 ms 262400 KB
test-1-02.txt MLE 84 ms 262400 KB
test-1-03.txt MLE 84 ms 262400 KB
test-1-04.txt MLE 84 ms 262400 KB
test-1-05.txt MLE 84 ms 262400 KB
test-1-06.txt MLE 84 ms 262400 KB
test-1-07.txt MLE 85 ms 262400 KB
test-1-08.txt MLE 84 ms 262400 KB
test-1-09.txt MLE 84 ms 262400 KB
test-1-10.txt MLE 84 ms 262400 KB
test-1-11.txt MLE 86 ms 262400 KB
test-1-12.txt MLE 84 ms 262400 KB
test-1-13.txt MLE 83 ms 262400 KB
test-1-14.txt MLE 84 ms 262400 KB
test-1-15.txt MLE 83 ms 262400 KB
test-2-01.txt MLE 84 ms 262400 KB
test-2-02.txt MLE 85 ms 262400 KB
test-2-03.txt MLE 84 ms 262400 KB
test-2-04.txt MLE 85 ms 262400 KB
test-2-05.txt MLE 88 ms 262400 KB
test-2-06.txt MLE 161 ms 262400 KB
test-2-07.txt MLE 138 ms 262400 KB
test-2-08.txt MLE 142 ms 262400 KB
test-2-09.txt MLE 124 ms 262400 KB
test-2-10.txt MLE 186 ms 262400 KB