QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#357388 | #404. Solitaire | RuchamCiMatke | 10 | 20ms | 41136kb | C++20 | 1.7kb | 2024-03-18 20:57:31 | 2024-03-18 20:57:32 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<20;
string tab[N];
ll dp[N];
pair<int, int> fre[N];
bool Chk(pair<int, int> a, int n, int m)
{
if(a.st != 1 && a.st != n)
if(tab[a.st - 1][a.nd] == 'o' && tab[a.st + 1][a.nd] == 'o')
return true;
if(a.nd != 1 && a.nd != m)
if(tab[a.st][a.nd - 1] == 'o' && tab[a.st][a.nd + 1] == 'o')
return true;
return false;
}
void Solve()
{
int n, m, l = 0;
cin >> m; n = 3;
for(int i = 1; i <= n; ++i)
{
cin >> tab[i]; tab[i] = '#' + tab[i];
for(int j = 1; j <= m; ++j)
if(tab[i][j] == 'x')
{
fre[l] = make_pair(i, j);
++l;
}
}
dp[0] = 1LL;
for(int i = 1; i < (1<<l); ++i)
{
for(int j = 0; j < l; ++j)
if((1<<j) & i) tab[fre[j].st][fre[j].nd] = 'o';
for(int j = 0; j < l; ++j)
{
if(!((1<<j) & i)) continue;
if(Chk(fre[j], n, m))
dp[i] += dp[i ^ (1<<j)];
}
dp[i] %= M;
for(int j = 0; j < l; ++j)
if((1<<j) & i) tab[fre[j].st][fre[j].nd] = 'x';
}
cout << dp[(1<<l) - 1] << "\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//int t; cin >> t;
//while(t--)
Solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 11ms
memory: 40376kb
input:
21 ooooxoooooxoooooxoooo oooxooooooooxxxxxooxo ooxooooooooooooooooxo
output:
319334400
result:
ok single line: '319334400'
Test #2:
score: 0
Accepted
time: 9ms
memory: 39776kb
input:
27 oxoooxooooooooooooooooooooo ooooooxxxxoooooxoxooooxoooo oooxooxooxoooxoooxoooooxooo
output:
188603933
result:
ok single line: '188603933'
Test #3:
score: 0
Accepted
time: 3ms
memory: 40580kb
input:
20 oooooooooxooooxoooxo oxoxoooooooxooooooxo ooooooooxooooooooooo
output:
40320
result:
ok single line: '40320'
Test #4:
score: 0
Accepted
time: 13ms
memory: 38816kb
input:
13 ooxoxoxooxooo xoxxxoxxxooxo ooooxoxoxoxoo
output:
22599513
result:
ok single line: '22599513'
Test #5:
score: 0
Accepted
time: 17ms
memory: 40088kb
input:
13 oxoxooxooxooo xooxxxxoxoxxx ooxooooxoxooo
output:
17662907
result:
ok single line: '17662907'
Test #6:
score: 0
Accepted
time: 10ms
memory: 38700kb
input:
11 oxoxoxoxoxo xxxxoxoxoxo oxoxoxooxoo
output:
891195994
result:
ok single line: '891195994'
Test #7:
score: 0
Accepted
time: 10ms
memory: 39808kb
input:
14 ooxoooxoxoooxo xoxxooooxxxoxx oooxoxooooxoxo
output:
549439514
result:
ok single line: '549439514'
Test #8:
score: 0
Accepted
time: 13ms
memory: 41136kb
input:
14 ooxoooooxooxoo xxxxxxoxxoxoox oxoooooxoxoooo
output:
278974156
result:
ok single line: '278974156'
Test #9:
score: 0
Accepted
time: 10ms
memory: 40784kb
input:
11 ooxooxoxoxo xxxxxoooxox oxoxoxoxoxo
output:
591208466
result:
ok single line: '591208466'
Test #10:
score: 0
Accepted
time: 12ms
memory: 38552kb
input:
11 ooxoxoxooxo xxoooxxxxxx ooxoxoxoxoo
output:
966753075
result:
ok single line: '966753075'
Test #11:
score: 0
Accepted
time: 12ms
memory: 39656kb
input:
15 oooxooooxooxooo oxooxxoooxxxxxx ooooxoxoooxoxoo
output:
727472313
result:
ok single line: '727472313'
Test #12:
score: 0
Accepted
time: 20ms
memory: 38744kb
input:
10 oxoxooxooo xxxxxoxxxx oxoxoxoxoo
output:
377955629
result:
ok single line: '377955629'
Subtask #2:
score: 0
Wrong Answer
Test #13:
score: 0
Wrong Answer
time: 0ms
memory: 38740kb
input:
880 ooxooooooxoxoooxoxoooooxooxooooxoxooooooooooooooxooooooxoxooooxooooxoxooooooxoxooooooooooxoxooooxooxooxoooooooooooxoxoooooxoooooxoxoxooxoooxooxooooxooooxoxoxoooxoooooxoooxooxoxoooooooxooooxooooooxooooxoxooxoooooxoxooooxooxooooooooooooooxoooooooooooxooooooooooooooxooooxoxoxooooooxooooooooxooooxoo...
output:
14241407
result:
wrong answer 1st lines differ - expected: '934647418', found: '14241407'
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%