QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#820772 | #3162. Mini Battleship | umd-red# | AC ✓ | 537ms | 3820kb | C++20 | 4.7kb | 2024-12-19 01:20:48 | 2024-12-19 01:20:48 |
Judging History
answer
//Remember: (a mod m)/b IS NOT (a/b) mod m
//Checklist: multitest (!!), maxn, mod, constraints, NEGATIVE ANSWER
#include <iostream>
#include<map>
#include<set>
#include<vector>
#include<string>
#include<queue>
#include<random>
#include<stack>
#include<chrono>
#include<bitset>
using namespace std;
//#define labeltc
#define endl "\n"
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ld long double
#define MOD 1000000007
//#define MOD 998244353
#define INFLL 2000000000001000000LL
#define INFI 1001000000
#define PI ((ld)(M_PI))
#define pii pair<int,int>
#define piii tuple<int,int,int>
#define pll pair<ll,ll>
#define plll tuple<ll,ll,ll>
#define fi first
#define sc second
#define m_p make_pair
#define p_b emplace_back
#define l_b lower_bound
#define u_b upper_bound
#define vi vector<int>
#define vl vector<ll>
#define rand_num(x,y) uniform_int_distribution<ll>((ll)x,(ll)y)(rng)
#define lsb(x) (x&(-x))
#define dgt(x) (x-'0')
#define all(x) x.begin(),x.end()
#define pans(x) ((x)? "YES " : "NO ")
template<typename T> bool ckmin(T& a, const T& b) {return (a>b)? a = b, 1 : 0;}
template<typename T> bool ckmax(T& a, const T& b) {return (a<b)? a = b, 1 : 0;}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll power(ll x, ll e, ll m){
ll r = 1;
while(e>0){
if(e%2) r = (r*x)%m;
x = (x*x)%m;
e >>= 1;
}
return r;
}
template <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T,U>& v){
os << v.fi << " " << v.sc;
return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v){
for (int i = 0; i < v.size(); ++i) {os << v[i] << " ";}
return os;
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& v){
for (auto it : v) {os << it << " ";}
return os;
}
template <typename T, typename U>
ostream& operator<<(ostream& os, const map<T,U>& v){
for (auto it : v) {os << it << "\n";}
return os;
}
template <typename T, typename U, typename W>
ostream& operator<<(ostream& os, const tuple<T,U,W>& v){
os << sp(get<0>(v)) << sp(get<1>(v)) << sp(get<2>(v));
return os;
}
void setIO(string s) {
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
int n,k,x[6];
int ans,tot;
vector<bitset<25>> all[6];
void precomp(){
for (int i=0; i<25; i++){
bitset<25> z;
z.set(i);
all[1].push_back(z);
}
for (int len=1; len<=4; len++) {
for (int i = 0; i < 5; i++) {
for (int j = 0; j + len < 5; j++) {
bitset<25> z, y;
for (int l = 0; l <= len; l++) {
z.set(5 * i + j + l);
y.set(5 * j + i + 5 * l);
}
all[len + 1].push_back(z);
all[len + 1].push_back(y);
}
}
}
}
void solve(){
cin >> n >> k;
bitset<25> bad,good;
for (int i=0; i<n; i++){
string row; cin >> row;
for (int j=0; j<n; j++){
if(row[j] == 'O'){
good.set(5*i+j);
}
else if(row[j] == 'X'){
bad.set(5*i+j);
}
}
}
if(n<5){
for (int i=n; i<5; i++){
for (int j=0; j<5; j++){
bad.set(5*i+j);
bad.set(5*j+i);
}
}
}
for (int i=0; i<k; i++){
cin >> x[i];
tot += x[i];
}
bitset<25> emp;
all[0].p_b(emp);
for (auto c: all[x[0]]){
for(bitset<25> y: all[x[1]]){
for (bitset<25> z: all[x[2]]){
for (bitset<25> a: all[x[3]]){
for (bitset<25> b: all[x[4]]){
bitset<25> cand;
cand |= c;
cand |= y;
cand |= z;
cand |= a;
cand |= b;
int cur = cand.count();
if(cur == tot){
cand |= good;
if(cand.count() == cur){
cand ^= bad;
if(cand.count()-bad.count() == cur){
ans++;
}
}
}
}
}
}
}
}
cout << ans << endl;
}
signed main(){
//setIO();
ios_base::sync_with_stdio(0);
cin.tie(NULL);
precomp();
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3528kb
input:
4 3 .... .OX. .... O..X 3 2 1
output:
132
result:
ok single line: '132'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3796kb
input:
4 4 .X.X .XX. ...X .... 1 2 3 4
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
2 2 .. .. 2 2
output:
4
result:
ok single line: '4'
Test #4:
score: 0
Accepted
time: 23ms
memory: 3552kb
input:
5 5 ..... ..... ..... ..... ..... 5 4 3 3 2
output:
80848
result:
ok single line: '80848'
Test #5:
score: 0
Accepted
time: 88ms
memory: 3528kb
input:
5 5 ..... ..... ..... ..... ..... 1 1 1 1 1
output:
6375600
result:
ok single line: '6375600'
Test #6:
score: 0
Accepted
time: 537ms
memory: 3820kb
input:
5 5 ..... ..... ..... ..... ..... 2 2 2 2 2
output:
18840000
result:
ok single line: '18840000'
Test #7:
score: 0
Accepted
time: 21ms
memory: 3656kb
input:
5 5 ..... XX... ..XXX XXXX. ....X 5 1 4 2 3
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 20ms
memory: 3488kb
input:
5 5 OOOOO XXOOO OOXXX XXXXO OOOOX 5 1 4 2 3
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 20ms
memory: 3660kb
input:
5 5 OOOOO ..OOO OO... ....O OOOO. 5 1 4 2 3
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 17ms
memory: 3588kb
input:
5 5 OOOOO OOOOO OOOOO OOOOO OOOOO 5 1 4 2 3
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
5 5 OOOOO OOOOO OOOOO OOOOO OOOOO 5 5 5 5 5
output:
240
result:
ok single line: '240'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
1 1 . 1
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
1 1 O 1
output:
1
result:
ok single line: '1'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
1 1 X 1
output:
0
result:
ok single line: '0'
Test #15:
score: 0
Accepted
time: 10ms
memory: 3620kb
input:
4 5 .... .... .... .... 4 4 4 4 4
output:
0
result:
ok single line: '0'
Test #16:
score: 0
Accepted
time: 87ms
memory: 3612kb
input:
5 5 OX.XO XX.XX ..... XX.XX OX.XO 1 1 2 1 1
output:
192
result:
ok single line: '192'
Test #17:
score: 0
Accepted
time: 133ms
memory: 3744kb
input:
5 5 OX.XO XX.XX ..... XX.XX OX.XO 1 1 2 2 1
output:
0
result:
ok single line: '0'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
2 2 O. .X 2 1
output:
2
result:
ok single line: '2'
Test #19:
score: 0
Accepted
time: 385ms
memory: 3516kb
input:
3 5 ... ... ... 2 2 1 2 2
output:
432
result:
ok single line: '432'
Test #20:
score: 0
Accepted
time: 14ms
memory: 3580kb
input:
5 4 O...O ..... ..O.. ..... O...O 2 2 2 2
output:
0
result:
ok single line: '0'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
3 2 O.O .X. ... 3 2
output:
8
result:
ok single line: '8'
Test #22:
score: 0
Accepted
time: 49ms
memory: 3584kb
input:
5 5 X...O ..... O...X O.X.. ..... 1 1 2 2 5
output:
6856
result:
ok single line: '6856'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
3 3 .O. ... OO. 3 2 2
output:
44
result:
ok single line: '44'
Test #24:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
4 3 .... ..X. .... O..X 4 3 1
output:
70
result:
ok single line: '70'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3756kb
input:
3 3 O.X .X. XO. 1 3 3
output:
0
result:
ok single line: '0'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
2 2 O. .. 1 2
output:
6
result:
ok single line: '6'
Test #27:
score: 0
Accepted
time: 4ms
memory: 3552kb
input:
4 4 .X.. ..XX .O.. X..O 1 3 1 1
output:
714
result:
ok single line: '714'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
2 2 .. OO 1 2
output:
4
result:
ok single line: '4'
Test #29:
score: 0
Accepted
time: 6ms
memory: 3616kb
input:
4 4 .... O... .... .OO. 3 1 1 2
output:
2390
result:
ok single line: '2390'
Test #30:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
3 3 ... .X. .XO 2 1 2
output:
36
result:
ok single line: '36'
Test #31:
score: 0
Accepted
time: 23ms
memory: 3576kb
input:
5 5 O.X.O O...O XO... .X.X. .O... 1 3 1 3 5
output:
48
result:
ok single line: '48'
Test #32:
score: 0
Accepted
time: 42ms
memory: 3656kb
input:
5 5 OO.X. ....X X.... ..... ..... 2 2 5 4 2
output:
3204
result:
ok single line: '3204'
Test #33:
score: 0
Accepted
time: 9ms
memory: 3816kb
input:
5 5 ..OX. ..X.. ..... O.... OXX.. 5 1 1 2 5
output:
556
result:
ok single line: '556'
Test #34:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
5 2 ..... ..X.. .X... ...O. ..... 2 4
output:
112
result:
ok single line: '112'
Test #35:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
2 2 .. O. 1 1
output:
6
result:
ok single line: '6'
Test #36:
score: 0
Accepted
time: 4ms
memory: 3660kb
input:
5 4 .X.X. X..O. ...O. ..... X..X. 1 3 4 2
output:
2722
result:
ok single line: '2722'
Test #37:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
3 3 O.. XO. .O. 1 1 2
output:
20
result:
ok single line: '20'
Test #38:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
4 3 ...O ..O. .... .... 1 1 1
output:
84
result:
ok single line: '84'
Test #39:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
2 2 .. X. 1 2
output:
2
result:
ok single line: '2'
Test #40:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
4 3 X..O .... O... .X.. 1 4 2
output:
63
result:
ok single line: '63'
Test #41:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
2 2 .O .X 2 2
output:
0
result:
ok single line: '0'
Test #42:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
4 2 ...O .... .... .... 4 2
output:
44
result:
ok single line: '44'
Test #43:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
4 2 XO.. .... X... .X.. 4 4
output:
0
result:
ok single line: '0'
Test #44:
score: 0
Accepted
time: 2ms
memory: 3656kb
input:
4 4 ..O. .... ..X. .XOO 4 4 1 1
output:
8
result:
ok single line: '8'
Test #45:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
4 2 .... .... .... ..X. 2 2
output:
334
result:
ok single line: '334'