QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#590538#8065. Thwack!nickbelov#AC ✓35ms4016kbC++203.6kb2024-09-26 02:30:402024-09-26 02:30:40

Judging History

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

  • [2024-09-26 02:30:40]
  • 评测
  • 测评结果:AC
  • 用时:35ms
  • 内存:4016kb
  • [2024-09-26 02:30:40]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
ostream_iterator<T> oit(const string &s = " "){ return ostream_iterator<T>(cout,s.c_str()); }
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
#define A(a) begin(a),end(a)
inline auto len = ranges::ssize;

struct chash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vii = vector<vector<int>>;
typedef vector<ll> vll;
using pll = pair<ll,ll>;
using pii = pair<int,int>;

constexpr ll NN = 100, M = 1000000007, L = 20;


int dp[NN][NN][2][2];
string s;int n;
int rec(int l,int r,char lc,char rc){
    if(l>=r) return 0;
    int &state = dp[l][r][lc=='W'][rc=='W'];
    if(state not_eq -1) return state;

    state=0;
    set<int> st;
    for(int i : rep(l,r)){
        char c1 = (i==l ? lc : s[i]);
        char c2 = ((i+1)==r ? rc : s[i+1]);
        if(c1 not_eq c2){
            st.insert(rec(l,i,lc,c2)^rec(i+2,r,s[i+2],rc)); //i+1 eats i
            st.insert(rec(i+1,r,c1,rc)^rec(l,i-1,lc,(i ? s[i-1] : 'W')));//i eats i+1
        }
    }

    while(st.contains(state)) ++state;
    // cout << l << " " << r << " " << lc << " " << rc << endl;
    // cout << "\t" << state << endl;
    return state;
}


void run()
{
    cin >> n >> s;   s += "padding";
    vector<pii> v; int l = 0;
    for(int r : rep(n)){
        if(s[r]=='.' and s[l]!='.') v.emplace_back(l,r-1);
        if(s[r]=='.')l=r+1;
    } if(l<n) v.emplace_back(l,n-1);


    int nimber = 0;
    for(auto [l,r] : v){
        nimber ^= rec(l,r,s[l],s[r]);
    }
    if(nimber){
        vector<pii> ans;
        for(auto [l,r] : v){
            auto og = rec(l,r,s[l],s[r]);
            auto need = nimber^og;

            for(int i : rep(l,r)){
                if(s[i] != s[i+1]){
                    auto x1 = rec(l,i,s[l],s[i+1]);
                    auto x2 = rec(i+2,r,s[i+2],s[r]);
                    if((x1^x2)==need) ans.emplace_back(i+1,i);
                    x1 = rec(i+1,r,s[i],s[r]);
                    x2 = rec(l,i-1,s[l], (i ? s[i-1] : 'W') );
                    if((x1^x2)==need) ans.emplace_back(i,i+1);
                }
            }
        } ranges::sort(ans);
        cout << len(ans) << '\n';
        for(auto [x,y] : ans) cout <<x+1 << " " << y+1 << '\n';
    }else cout << "0\n";
}

int main()
{
    //KING OF THE WORLD...... U.W.T.B
    std::cin.tie(0);
    ios_base::sync_with_stdio(false);
    for(auto &v : dp) for(auto &vv : v) for(auto &vvv: vv) for(auto &x : vvv) x=-1;
    run();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3712kb

input:

4
BWBW

output:

2
2 3
3 2

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

11
.BW.WB..W..

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

8
BBBBW.BW

output:

1
5 4

result:

ok 2 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

9
BBBBBW.BW

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

12
WBBWBWWBBWBW

output:

5
2 1
4 5
5 4
10 11
11 10

result:

ok 6 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

11
WBBWWWBBWBW

output:

5
1 2
4 3
9 10
10 9
11 10

result:

ok 6 lines

Test #7:

score: 0
Accepted
time: 35ms
memory: 3704kb

input:

100
BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW

output:

56
2 1
3 2
3 4
6 5
6 7
13 14
14 15
15 14
17 18
18 17
19 18
21 20
25 24
26 25
26 27
29 28
29 30
33 34
35 34
36 37
37 38
38 37
40 41
41 40
42 41
43 44
49 48
49 50
52 51
52 53
58 57
59 60
60 61
61 60
63 64
64 63
65 64
66 67
68 67
72 71
72 73
75 74
75 76
76 77
80 81
82 83
83 84
84 83
86 87
87 86
88 87
9...

result:

ok 57 lines

Test #8:

score: 0
Accepted
time: 34ms
memory: 3948kb

input:

99
BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWB

output:

26
2 1
10 11
11 12
13 14
18 17
20 19
22 21
25 24
34 35
36 37
41 40
43 42
45 44
55 56
57 58
59 60
64 63
66 65
75 76
78 79
80 81
82 83
87 86
89 88
90 89
98 99

result:

ok 27 lines

Test #9:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

1
.

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

100
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

100
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB

output:

0

result:

ok single line: '0'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

100
....................................................................................................

output:

0

result:

ok single line: '0'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

5
.W.B.

output:

0

result:

ok single line: '0'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3952kb

input:

1
B

output:

0

result:

ok single line: '0'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

1
W

output:

0

result:

ok single line: '0'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3748kb

input:

2
BW

output:

2
1 2
2 1

result:

ok 3 lines

Test #17:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

2
WB

output:

2
1 2
2 1

result:

ok 3 lines

Test #18:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

2
..

output:

0

result:

ok single line: '0'

Test #19:

score: 0
Accepted
time: 0ms
memory: 4016kb

input:

2
BB

output:

0

result:

ok single line: '0'

Test #20:

score: 0
Accepted
time: 0ms
memory: 4000kb

input:

2
WW

output:

0

result:

ok single line: '0'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

3
B.W

output:

0

result:

ok single line: '0'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

98
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWBBWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

output:

0

result:

ok single line: '0'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

97
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBWWBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB

output:

2
49 48
50 51

result:

ok 3 lines

Test #24:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

100
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

output:

2
49 50
51 50

result:

ok 3 lines

Test #25:

score: 0
Accepted
time: 0ms
memory: 3716kb

input:

99
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

output:

2
49 50
51 50

result:

ok 3 lines

Test #26:

score: 0
Accepted
time: 26ms
memory: 3712kb

input:

100
WWBBWBWBBWWWBWWBWWWWBWWWBBBWWWBWBWWBWBWWBBWBBWBWBWWBBBWWBWWWWWWWWBWBWBBBWWBBWWWWWWWBWBWWWWWWBWWWWBWB

output:

0

result:

ok single line: '0'

Test #27:

score: 0
Accepted
time: 1ms
memory: 3744kb

input:

100
WWB.BBBBWWWBBWWBBWBWWBB.WWWBWBWWB.BBBBBBWBBWBB.W.WWBWWWBWBWBWWWBWBWB..BWB..WWWB.WBWBWW.BWBWW.BBBB..W

output:

0

result:

ok single line: '0'

Test #28:

score: 0
Accepted
time: 29ms
memory: 3760kb

input:

100
WWBWBBWBWBBWBWWWWBWWWBBWBBWBBBWWBBBBBWBBWBBWBBWWWBWWBWWBBWBBBBWWBBWBWBWBBBBWBBBWWWWBBWBBBBWBWWBBWBWB

output:

4
3 4
38 37
38 39
53 54

result:

ok 5 lines

Test #29:

score: 0
Accepted
time: 28ms
memory: 3976kb

input:

100
BBBWBWWWBBBWWWBWWBWWBWBBWBWWBBWWBWBWBBBBWWBWWBWBBBWWWWWBWWWWWWBWBWBBBWWBWBBWBBWBBBBBWBBBBBWBWWBBWBBW

output:

6
32 33
35 36
37 36
47 46
56 57
62 63

result:

ok 7 lines

Test #30:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

100
..WW.WBB.BBWWWWW.WW.B.WWB...W.BWBB.BBBWWB..BW..W.BWW.BWBW...BBB..W..BB.BBBB.BBBW.W.WW......BWW.W.WW.

output:

9
12 11
38 39
40 41
41 40
44 45
45 44
54 55
57 56
79 80

result:

ok 10 lines

Test #31:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

100
.WBBWBB..BW.BWBB.BBWW...B.WWWBWBBWWBWWW.W.WWWWB.W.B......W.B.W.W.BB.W..WWBB....WBBWW..WB..BW.B...BBW

output:

3
29 30
33 34
36 35

result:

ok 4 lines

Test #32:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

100
BWB..B.BB..BBWBW.BBW.B.WWB..WB.BWB...BB.BWBBBBBWW.BWWBWW.BWW.BBBW..BW..WW.WBW.BWWWBB.WBB.WWB.W..B.B.

output:

10
13 14
15 16
20 19
26 25
42 43
54 55
58 59
65 64
86 87
92 91

result:

ok 11 lines

Test #33:

score: 0
Accepted
time: 3ms
memory: 3708kb

input:

100
BBBBBBBBBBBWBBBBBBBWBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBWBBBBBBBBBBBBBBBBBWBBBBBBBWBBBBBBB

output:

3
67 66
92 93
94 93

result:

ok 4 lines

Test #34:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

100
WBWWWWWWWWWW....WWWWWBBBWBWW.W.WWBWWWWWBBWWWBWWWWWWWWB.BWWBW.WBBBWW.WBWWWBBWBW.WWWWWWWWWWWWBWBWWWWWW

output:

2
45 44
54 53

result:

ok 3 lines

Test #35:

score: 0
Accepted
time: 0ms
memory: 3936kb

input:

100
W.B.B.W...B.BW.B.BB.WWWBBW.WB...W.B...WW..B.WWWBB..W.WW.B....WBB..WW..B.WWW.BB.BBB.BB.W.BWWBW..WWBW.

output:

0

result:

ok single line: '0'

Test #36:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

100
WBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB

output:

1
2 1

result:

ok 2 lines

Test #37:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

100
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWB

output:

1
99 100

result:

ok 2 lines