QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#820772#3162. Mini Battleshipumd-red#AC ✓537ms3820kbC++204.7kb2024-12-19 01:20:482024-12-19 01:20:48

Judging History

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

  • [2024-12-19 01:20:48]
  • 评测
  • 测评结果:AC
  • 用时:537ms
  • 内存:3820kb
  • [2024-12-19 01:20:48]
  • 提交

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'