QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#590538 | #8065. Thwack! | nickbelov# | AC ✓ | 35ms | 4016kb | C++20 | 3.6kb | 2024-09-26 02:30:40 | 2024-09-26 02:30:40 |
Judging History
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