QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#357304 | #404. Solitaire | weajink2 | 10 | 6ms | 4344kb | C++14 | 1.4kb | 2024-03-18 20:03:30 | 2024-03-18 20:03:32 |
Judging History
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%