QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#357210 | #404. Solitaire | Arapak2 | 10 | 7ms | 3828kb | C++20 | 1.8kb | 2024-03-18 19:21:15 | 2024-03-18 19:22:20 |
Judging History
answer
// Author: Kajetan Ramsza
#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template<typename F, typename S> ostream& operator<<(ostream& os, const pair<F, S> &p) { return os<<"("<<p.first<<", "<<p.second<<")"; }
template<typename T> ostream &operator<<(ostream & os, const vector<T> &v) { os << "{"; typename vector< T > :: const_iterator it;
for( it = v.begin(); it != v.end(); it++ ) { if( it != v.begin() ) os << ", "; os << *it; } return os << "}"; }
void dbg_out() { cerr<<'\n'; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr<<' '<<H; dbg_out(T...); }
#ifdef DEBUG
#define dbg(...) cerr<<"(" << #__VA_ARGS__ <<"):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
const ll mod = 1e9 + 7;
int n;
vector<array<int, 3>> board;
vector<pii> pawns;
vector<ll> dp;
ll solve(int mask) {
if(dp[mask] != -1) return dp[mask];
vector<array<int, 3>> curr(board);
rep(i,0,sz(pawns))
if((mask>>i) & 1)
curr[pawns[i].first][pawns[i].second] = true;
ll res = 0;
rep(id,0,sz(pawns)) {
auto [i,j] = pawns[id];
if(curr[i][j]) continue;
if((i > 0 && i < n-1 && curr[i-1][j] && curr[i+1][j]) ||
(j == 1 && curr[i][j-1] && curr[i][j+1]))
res = (res + solve(mask | (1<<id))) % mod;
}
return dp[mask] = res;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
board.resize(n);
rep(j,0,3) rep(i,0,n) {
char c; cin>>c;
board[i][j] = c == 'o';
if(!board[i][j]) pawns.push_back({i, j});
}
dp.assign(1<<sz(pawns), -1);
dp[(1<<sz(pawns))-1] = 1;
cout<<solve(0)<<'\n';
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 3792kb
input:
21 ooooxoooooxoooooxoooo oooxooooooooxxxxxooxo ooxooooooooooooooooxo
output:
319334400
result:
ok single line: '319334400'
Test #2:
score: 0
Accepted
time: 4ms
memory: 3540kb
input:
27 oxoooxooooooooooooooooooooo ooooooxxxxoooooxoxooooxoooo oooxooxooxoooxoooxoooooxooo
output:
188603933
result:
ok single line: '188603933'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
20 oooooooooxooooxoooxo oxoxoooooooxooooooxo ooooooooxooooooooooo
output:
40320
result:
ok single line: '40320'
Test #4:
score: 0
Accepted
time: 5ms
memory: 3828kb
input:
13 ooxoxoxooxooo xoxxxoxxxooxo ooooxoxoxoxoo
output:
22599513
result:
ok single line: '22599513'
Test #5:
score: 0
Accepted
time: 7ms
memory: 3632kb
input:
13 oxoxooxooxooo xooxxxxoxoxxx ooxooooxoxooo
output:
17662907
result:
ok single line: '17662907'
Test #6:
score: 0
Accepted
time: 6ms
memory: 3636kb
input:
11 oxoxoxoxoxo xxxxoxoxoxo oxoxoxooxoo
output:
891195994
result:
ok single line: '891195994'
Test #7:
score: 0
Accepted
time: 5ms
memory: 3580kb
input:
14 ooxoooxoxoooxo xoxxooooxxxoxx oooxoxooooxoxo
output:
549439514
result:
ok single line: '549439514'
Test #8:
score: 0
Accepted
time: 3ms
memory: 3560kb
input:
14 ooxoooooxooxoo xxxxxxoxxoxoox oxoooooxoxoooo
output:
278974156
result:
ok single line: '278974156'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3760kb
input:
11 ooxooxoxoxo xxxxxoooxox oxoxoxoxoxo
output:
591208466
result:
ok single line: '591208466'
Test #10:
score: 0
Accepted
time: 5ms
memory: 3608kb
input:
11 ooxoxoxooxo xxoooxxxxxx ooxoxoxoxoo
output:
966753075
result:
ok single line: '966753075'
Test #11:
score: 0
Accepted
time: 5ms
memory: 3584kb
input:
15 oooxooooxooxooo oxooxxoooxxxxxx ooooxoxoooxoxoo
output:
727472313
result:
ok single line: '727472313'
Test #12:
score: 0
Accepted
time: 4ms
memory: 3636kb
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
Time Limit Exceeded
Test #38:
score: 0
Time Limit Exceeded
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%