QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#357304#404. Solitaireweajink210 6ms4344kbC++141.4kb2024-03-18 20:03:302024-03-18 20:03:32

Judging History

你现在查看的是最新测评结果

  • [2024-03-18 20:03:32]
  • 评测
  • 测评结果:10
  • 用时:6ms
  • 内存:4344kb
  • [2024-03-18 20:03:30]
  • 提交

answer

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

const ll mod = 1e9+7;
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll i;
	ll n;
	cin>>n;
	string tab[3];
	pair<ll,ll> gdzie[20];
	ll indeks[3][n];
	ll pt = 0;
	for (i = 0; i < 3; i++){
		cin>>tab[i];
		for (ll j = 0; j < n; j++){
			if (tab[i][j] == 'x'){
				gdzie[pt] = {i,j};
				indeks[i][j] = pt;
				pt++;
			}	
		}
	}
	if (pt > 16){
		cout<<0<<"\n";
		return 0;
	}	
	ll dp[(1<<pt)];
	for (i = 0; i < (1<<pt); i++) dp[i] = 0;
	dp[0] = 1;
	for (i = 0; i < (1<<pt); i++){
		//cout<<bitset<i<<" # "<<dp[i]<<"\n";
		for (ll j = 0; j < pt; j++){
			if (i&(1<<j)) continue;
			pair<ll,ll> pole = gdzie[j];
			//Góra-dół
			if (pole.first == 1){
				if (tab[pole.first-1][pole.second] == 'o' || i&(1<<indeks[pole.first-1][pole.second])){
					if (tab[pole.first+1][pole.second] == 'o' || i&(1<<indeks[pole.first+1][pole.second])){
						dp[i^(1<<j)] = (dp[i^(1<<j)]+dp[i])%mod;
						continue;
					}
				}
			}
			//Lewo-prawo
			if (pole.second != 0 && pole.second != n-1){
				if (tab[pole.first][pole.second-1] == 'o' || i&(1<<indeks[pole.first][pole.second-1])){
					if (tab[pole.first][pole.second+1] == 'o' || i&(1<<indeks[pole.first][pole.second+1])){
						dp[i^(1<<j)] = (dp[i^(1<<j)]+dp[i])%mod;
					}
				}
			}
		}
	}
	cout<<dp[(1<<pt)-1]%mod<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 1ms
memory: 3616kb

input:

21
ooooxoooooxoooooxoooo
oooxooooooooxxxxxooxo
ooxooooooooooooooooxo

output:

319334400

result:

ok single line: '319334400'

Test #2:

score: 0
Accepted
time: 3ms
memory: 3840kb

input:

27
oxoooxooooooooooooooooooooo
ooooooxxxxoooooxoxooooxoooo
oooxooxooxoooxoooxoooooxooo

output:

188603933

result:

ok single line: '188603933'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

20
oooooooooxooooxoooxo
oxoxoooooooxooooooxo
ooooooooxooooooooooo

output:

40320

result:

ok single line: '40320'

Test #4:

score: 0
Accepted
time: 6ms
memory: 4096kb

input:

13
ooxoxoxooxooo
xoxxxoxxxooxo
ooooxoxoxoxoo

output:

22599513

result:

ok single line: '22599513'

Test #5:

score: 0
Accepted
time: 6ms
memory: 4052kb

input:

13
oxoxooxooxooo
xooxxxxoxoxxx
ooxooooxoxooo

output:

17662907

result:

ok single line: '17662907'

Test #6:

score: 0
Accepted
time: 3ms
memory: 4048kb

input:

11
oxoxoxoxoxo
xxxxoxoxoxo
oxoxoxooxoo

output:

891195994

result:

ok single line: '891195994'

Test #7:

score: 0
Accepted
time: 6ms
memory: 4272kb

input:

14
ooxoooxoxoooxo
xoxxooooxxxoxx
oooxoxooooxoxo

output:

549439514

result:

ok single line: '549439514'

Test #8:

score: 0
Accepted
time: 6ms
memory: 4000kb

input:

14
ooxoooooxooxoo
xxxxxxoxxoxoox
oxoooooxoxoooo

output:

278974156

result:

ok single line: '278974156'

Test #9:

score: 0
Accepted
time: 3ms
memory: 4344kb

input:

11
ooxooxoxoxo
xxxxxoooxox
oxoxoxoxoxo

output:

591208466

result:

ok single line: '591208466'

Test #10:

score: 0
Accepted
time: 6ms
memory: 4324kb

input:

11
ooxoxoxooxo
xxoooxxxxxx
ooxoxoxoxoo

output:

966753075

result:

ok single line: '966753075'

Test #11:

score: 0
Accepted
time: 6ms
memory: 3992kb

input:

15
oooxooooxooxooo
oxooxxoooxxxxxx
ooooxoxoooxoxoo

output:

727472313

result:

ok single line: '727472313'

Test #12:

score: 0
Accepted
time: 6ms
memory: 4088kb

input:

10
oxoxooxooo
xxxxxoxxxx
oxoxoxoxoo

output:

377955629

result:

ok single line: '377955629'

Subtask #2:

score: 0
Runtime Error

Test #13:

score: 0
Runtime Error

input:

880
ooxooooooxoxoooxoxoooooxooxooooxoxooooooooooooooxooooooxoxooooxooooxoxooooooxoxooooooooooxoxooooxooxooxoooooooooooxoxoooooxoooooxoxoxooxoooxooxooooxooooxoxoxoooxoooooxoooxooxoxoooooooxooooxooooooxooooxoxooxoooooxoxooooxooxooooooooooooooxoooooooooooxooooooooooooooxooooxoxoxooooooxooooooooxooooxoo...

output:


result:


Subtask #3:

score: 0
Runtime Error

Test #38:

score: 0
Runtime Error

input:

27
oxooooxooooooxoooxoooooxoxo
xxooxooooxxxoxoooxooxxxxxoo
ooxoxoxoxoooxoxooooxoxooxoo

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%