AtCoder Beginner Contest 025

Submission #3978508

Source codeソースコード

#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;
}

int 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

Task問題 D - 25個の整数
User nameユーザ名 env
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 2140 Byte
File nameファイル名
Exec time実行時間 105 ms
Memory usageメモリ使用量 131456 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample-01.txt,sample-02.txt,sample-03.txt,sample-04.txt
Subtask1 30 / 30 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 70 / 70 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample-01.txt AC 39 ms 131328 KB
sample-02.txt AC 39 ms 131328 KB
sample-03.txt AC 39 ms 131328 KB
sample-04.txt AC 39 ms 131328 KB
test-1-01.txt AC 39 ms 131328 KB
test-1-02.txt AC 39 ms 131328 KB
test-1-03.txt AC 39 ms 131456 KB
test-1-04.txt AC 39 ms 131328 KB
test-1-05.txt AC 39 ms 131328 KB
test-1-06.txt AC 39 ms 131328 KB
test-1-07.txt AC 39 ms 131328 KB
test-1-08.txt AC 39 ms 131328 KB
test-1-09.txt AC 40 ms 131328 KB
test-1-10.txt AC 39 ms 131328 KB
test-1-11.txt AC 39 ms 131328 KB
test-1-12.txt AC 39 ms 131328 KB
test-1-13.txt AC 39 ms 131328 KB
test-1-14.txt AC 39 ms 131328 KB
test-1-15.txt AC 40 ms 131328 KB
test-2-01.txt AC 40 ms 131328 KB
test-2-02.txt AC 40 ms 131328 KB
test-2-03.txt AC 39 ms 131328 KB
test-2-04.txt AC 40 ms 131328 KB
test-2-05.txt AC 43 ms 131328 KB
test-2-06.txt AC 83 ms 131328 KB
test-2-07.txt AC 72 ms 131328 KB
test-2-08.txt AC 79 ms 131328 KB
test-2-09.txt AC 72 ms 131328 KB
test-2-10.txt AC 105 ms 131328 KB