PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Utkarsh Gupta
Tester: Aryan Choudhary
Editorialist: Lavish Gupta
DIFFICULTY:
Easy-Medium, Medium
PREREQUISITES:
None
PROBLEM:
*This problem is similar to the problem "STRFLIP2". The only difference between them is the number of moves allowed — in this problem, up to N moves can be made.
You are given a binary string A of length N, which we treat as being 1-indexed.
In one move, you are allowed to
- Pick a contiguous substring (i.e. A[L:R] for some 1 \leq L \leq R \leq N) of A that contains at least one ‘0’ and at least one ‘1’
- Flip all the characters of the chosen substring (i.e. change every 0 to 1 and every 1 to 0)
You are also given a target string B of the same length as A.
Determine if it is possible to convert A to B by applying a sequence of moves as described above.
If it is possible to convert A to B, then find a sequence of no more than N moves that accomplishes this.
It can be shown that whenever it is possible to convert A to B, then it is possible to do so using no more than N moves.
If there are multiple answers, you can print any of them.
QUICK EXPLANATION:
First Observation
Let’s assume A is not equal to B.
We cannot apply any operation on the string A if it contains all 0's or all 1's. Similarly, if B contains all 0's or all 1's, we can never convert A into B.
When is it impossible to convert A to B?
Extending our observation 1 we can definitely say that if either A or B contains all 0's or all 1's and they are not equal then we cannot make them equal. Suppose both A and B contains at least one 0 and at least one 1. Can we always convert A to B? The answer is Yes!
Let’s look at the following approach.
Approach for N operations
Since we have N operations it looks like we can fix one index in each operation. Lets say we have some index x and x+1 such that A[x] \neq A[x+1].
Now using these two indices, we can first fix the indices [1 ... (x-1)], and [(x+2) ... N] (by always including indices x and x+1 in the chosen substring).
Finally, we will try to fix A[x] and A[x+1].
What should be the value of x
Note that at the end, we want to fix A[x] and A[x+1]. As we know, A[x] \neq A[x+1], it would be good if B[x] \neq B[x+1], so that we can easily fix both x and x+1 in at max one single operation.
So, we want to find such x : B[x] \neq B[x+1]. If A[x] = A[x+1] for this x, then we can choose one of A[1...x], A[(x+1)...N], and flip this substring to make A[x] \neq A[x+1]
Approach for N/2+10 operations
Term N/2 suggests that we should fix 2 indices in each operation. Lets try to modify the above approach.
Instead of using x and x+1 indices, let’s try to use N/2 and N/2 + 1 to make the whole string equal.
Now instead of fixing one index we will try to fix one index in left half (i.e. [1 ... N/2 - 1]) and one index in right half (i.e. [N/2 + 2 ... N].
Lets say L is the leftmost index such that A[L] \neq B[L] ( Let L = N/2 if there is no mismatching index in left half).
Similarly R is the rightmost index such that A[R] \neq B[R] (Let R = N/2+1 if there is no mismatching index in right half).
Now flipping [L,R] will fix two indexes (L and R). So after approximately N/2 operations we would have fixed every index apart from N/2 and N/2+1.
Fixing N/2 and N/2+1
Let x be any index such that B[x] \neq B[x+1].
If x=N/2 then flipping \{N/2, N/2+1\} will do our job.
Now let x < N/2, then flipping [x ... (N/2+1)] and [x ... N/2] would make values of A[N/2] = A[N/2+1]. Now we can fix x and x+1 which could be easily fixed.
EXPLANATION:
TIME COMPLEXITY:
SOLUTION:
Tester's Solution - STRFLIP
/* in the name of Anton */
/*
Compete against Yourself.
Author - Aryan (@aryanc403)
Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
template <class S,
S (*op)(S, S),
S (*e)(),
class F,
S (*mapping)(F, S),
F (*composition)(F, F),
F (*id)()>
struct lazy_segtree {
public:
lazy_segtree() : lazy_segtree(0) {}
explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = internal::ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
} // namespace atcoder
#ifdef ARYANC403
#include <header.h>
#else
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize ("-ffloat-store")
#include<bits/stdc++.h>
#define dbg(args...) 42;
#endif
// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
Fun fun_;
public:
template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
using namespace std;
#define fo(i,n) for(i=0;i<(n);++i)
#define repA(i,j,n) for(i=(j);i<=(n);++i)
#define repD(i,j,n) for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"
typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
vi readVectorInt(int n,lli l,lli r){
vi a(n);
for(int i=0;i<n-1;++i)
a[i]=readIntSp(l,r);
a[n-1]=readIntLn(l,r);
return a;
}
// #include<atcoder/dsu>
// vector<vi> readTree(const int n){
// vector<vi> e(n);
// atcoder::dsu d(n);
// for(lli i=1;i<n;++i){
// const lli u=readIntSp(1,n)-1;
// const lli v=readIntLn(1,n)-1;
// e[u].pb(v);
// e[v].pb(u);
// d.merge(u,v);
// }
// assert(d.size(0)==n);
// return e;
// }
const lli INF = 0xFFFFFFFFFFFFFFFL;
lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}
class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{ return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y )); }};
void add( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt==m.end()) m.insert({x,cnt});
else jt->Y+=cnt;
}
void del( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt->Y<=cnt) m.erase(jt);
else jt->Y-=cnt;
}
bool cmp(const ii &a,const ii &b)
{
return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}
const lli mod = 1000000007L;
// const lli maxN = 1000000007L;
lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
lli m;
string s;
vi a;
//priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .
struct S {
// # of 0 / # of 1
long long zero, one, inversion;
};
// swapping flag
using F = bool;
S op(S l, S r) {
return S{
l.zero + r.zero,
l.one + r.one,
};
}
S e() { return S{0, 0}; }
S mapping(F l, S r) {
if (!l) return r;
// swap
return S{r.one, r.zero};
}
F composition(F l, F r) { return (l && !r) || (!l && r); }
F id() { return false; }
int main(void) {
ios_base::sync_with_stdio(false);cin.tie(NULL);
// freopen("txt.in", "r", stdin);
// freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
auto isBinaryString=[&](const string s)->bool{
for(auto x:s){
if(x!='0'&&x!='1')
return false;
}
return true;
};
T=readIntLn(1,1e5);
lli sumN = 3e5;
while(T--)
{
const lli n=readIntLn(1,sumN);
sumN-=n;
const string s=readStringLn(n,n);
const string t=readStringLn(n,n);
assert(isBinaryString(s));
assert(isBinaryString(t));
if(s==t){
cout<<0<<endl;
continue;
}
atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(n);
for(int i=0;i<n;++i){
if(s[i]=='0')
seg.set(i,S{1,0});
else
seg.set(i,S{0,1});
}
vii ans;
auto change=[&](const lli l,const lli r){
ans.pb({l,r});
seg.apply(l,r+1,true);
};
auto getChr=[&](const lli pos)->char{
const auto g=seg.get(pos);
return g.one+'0';
};
lli ps=-1;
for(int i=0;i+1<n;++i){
if(t[i]!=t[i+1]){
ps=i;
break;
}
}
if(ps==-1){
cout<<-1<<endl;
continue;
}
if(s[ps]==s[ps+1]){
bool fl=false;
for(int i=0;i+1<n;++i){
if(s[i]!=s[i+1]){
if(i<ps)
change(i,ps);
else
change(ps+1,i+1);
fl=true;
break;
}
}
if(!fl){
cout<<-1<<endl;
continue;
}
}
for(int i=0;i<ps;++i){
if(getChr(i)==t[i])
continue;
change(i,ps+1);
}
for(int i=n-1;i>ps;--i){
if(getChr(i)==t[i])
continue;
change(ps,i);
}
for(int i=0;i<n;++i)
assert(getChr(i)==t[i]);
assert(sz(ans)<=n);
cout<<sz(ans)<<endl;
for(auto x:ans)
cout<<x.X+1<<" "<<x.Y+1<<endl;
} aryanc403();
readEOF();
return 0;
}
Tester's Solution - STRFLIP2
/* in the name of Anton */
/*
Compete against Yourself.
Author - Aryan (@aryanc403)
Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/
#ifdef ARYANC403
#include <header.h>
#else
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize ("-ffloat-store")
#include<bits/stdc++.h>
#define dbg(args...) 42;
#endif
// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
Fun fun_;
public:
template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
using namespace std;
#define fo(i,n) for(i=0;i<(n);++i)
#define repA(i,j,n) for(i=(j);i<=(n);++i)
#define repD(i,j,n) for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"
typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
vi readVectorInt(int n,lli l,lli r){
vi a(n);
for(int i=0;i<n-1;++i)
a[i]=readIntSp(l,r);
a[n-1]=readIntLn(l,r);
return a;
}
// #include<atcoder/dsu>
// vector<vi> readTree(const int n){
// vector<vi> e(n);
// atcoder::dsu d(n);
// for(lli i=1;i<n;++i){
// const lli u=readIntSp(1,n)-1;
// const lli v=readIntLn(1,n)-1;
// e[u].pb(v);
// e[v].pb(u);
// d.merge(u,v);
// }
// assert(d.size(0)==n);
// return e;
// }
const lli INF = 0xFFFFFFFFFFFFFFFL;
lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}
class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{ return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y )); }};
void add( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt==m.end()) m.insert({x,cnt});
else jt->Y+=cnt;
}
void del( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt->Y<=cnt) m.erase(jt);
else jt->Y-=cnt;
}
bool cmp(const ii &a,const ii &b)
{
return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}
const lli mod = 1000000007L;
// const lli maxN = 1000000007L;
lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
lli m;
string s;
vi a;
//priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .
int main(void) {
ios_base::sync_with_stdio(false);cin.tie(NULL);
// freopen("txt.in", "r", stdin);
// freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
auto isBinaryString=[&](const string s)->bool{
for(auto x:s){
if(x!='0'&&x!='1')
return false;
}
return true;
};
T=readIntLn(1,2e3);
lli sumN = 5e3;
while(T--)
{
const lli n=readIntLn(20,min(1000LL,sumN));
sumN-=n;
string s=readStringLn(n,n);
const string t=readStringLn(n,n);
assert(isBinaryString(s));
assert(isBinaryString(t));
if(s==t){
cout<<0<<endl;
continue;
}
vii ans;
auto change=[&](const lli l,const lli r,const bool fl){
ans.pb({l,r});
if(fl){
for(int i=l;i<=r;++i)
s[i]^=1;
}
};
auto getChr=[&](const lli pos,const bool fl=false)->char{
return s[pos]^fl;
};
lli ps=-1;
for(int i=0;i+1<n;++i){
if(t[i]!=t[i+1]){
ps=i;
break;
}
}
if(ps==-1){
cout<<-1<<endl;
continue;
}
const lli mid=n/2;
if(s[mid]==s[mid+1]){
bool fl=false;
for(int i=0;i+1<n;++i){
if(s[i]!=s[i+1]){
if(i<mid)
change(i,mid,true);
else
change(mid+1,i+1,true);
fl=true;
break;
}
}
if(!fl){
cout<<-1<<endl;
continue;
}
}
lli l=0,r=n-1;
bool flag=false;
while(true){
while(l<mid&&getChr(l,flag)==t[l]){
s[l]^=flag;
l++;
}
while(r>mid+1&&getChr(r,flag)==t[r]){
s[r]^=flag;
r--;
}
if(l==mid&&r==mid+1)
break;
change(l,r,false);
flag^=1;
}
s[mid]^=flag;
s[mid+1]^=flag;
flag=0;
if(getChr(mid)!=t[mid]){
if(getChr(mid+1)!=t[mid+1])
change(mid,mid+1,true);
else{
if(ps+1<mid){
change(ps,mid-1,true);
change(ps,mid,true);
}
else if(ps+1==mid){
change(mid,mid+1,true);
change(ps,mid+1,true);
change(ps,mid,true);
} else if(ps==mid){
/*
In this case we have -
getChr(mid)!=getChr(mid+1)
t[mid]! = getChr(mid)
t[mid+1] = getChr(mid+1)
Its impossible because these conditions implies t[mid]==t[mid+1]
ps by definition is t[ps]!=t[ps+1]
*/
assert(false);
} else{
change(mid,ps+1,true);
change(mid+1,ps+1,true);
}
}
} else {
if(getChr(mid+1)!=t[mid+1]){
if(ps<mid){
change(ps,mid,true);
change(ps,mid+1,true);
}
else if(ps==mid){
/*
In this case we have -
getChr(mid)!=getChr(mid+1)
t[mid] == getChr(mid)
t[mid+1] != getChr(mid+1)
Its impossible because these conditions implies t[mid]==t[mid+1]
ps by definition is t[ps]!=t[ps+1]
*/
assert(false);
} else if(ps==mid+1){
change(mid,mid+1,true);
change(mid,ps+1,true);
change(mid+1,ps+1,true);
}
else{
change(mid+1,ps+1,true);
change(mid+2,ps+1,true);
}
}
}
for(int i=0;i<n;++i)
assert(getChr(i)==t[i]);
assert(sz(ans)<=n/2+10);
cout<<sz(ans)<<endl;
cerr<<sz(ans)<<" "<<n/2+10<<endl;
for(auto x:ans)
cout<<x.X+1<<" "<<x.Y+1<<endl;
} aryanc403();
readEOF();
return 0;
}
Setter's Solution - STRFLIP
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
#define LL long long
LL seed = chrono::steady_clock::now().time_since_epoch().count();
mt19937_64 rng(seed);
#define rand(l, r) uniform_int_distribution<LL>(l, r)(rng)
clock_t start = clock();
#define getchar getchar_unlocked
namespace IO {
long long readInt(char endd) {
long long ret = 0;
char c = getchar();
while (c != endd) {
ret = (ret * 10) + c - '0';
c = getchar();
}
return ret;
}
long long readInt(long long L, long long R, char endd) {
long long ret = readInt(endd);
assert(ret >= L && ret <= R);
return ret;
}
long long readIntSp(long long L, long long R) {
return readInt(L, R, ' ');
}
long long readIntLn(long long L, long long R) {
return readInt(L, R, '\n');
}
string readString(int l, int r, char endd = '\n') {
string ret = "";
char c = getchar();
while (c == '0' || c == '?' || c == '1') {
ret += c;
c = getchar();
}
assert((int)ret.size() >= l && (int)ret.size() <= r);
assert(c == endd);
return ret;
}
}
using namespace IO;
const int TMAX = 1'00'000;
const int N = 1'00'000;
const int SUM_N = 3'00'000;
int sum_n = 0;
void solve() {
int n = readIntLn(1, N);
sum_n += n;
string s = readString(n, n);
string t = readString(n, n);
if (s == t) {
cout << "0\n";
return;
}
bool all_same = true;
int I;
for (int i=1;i<n;++i) {
if (t[i] != t[i-1]) {
all_same = false;
I = i;
break;
}
}
if (all_same) {
cout << "-1\n";
return;
}
all_same = true;
for (int i=1;i<n;++i) {
if (s[i] != s[i-1]) {
all_same = false;
break;
}
}
if (all_same) {
cout << "-1\n";
return;
}
vector<array<int, 2>> ans;
if (s[I] == s[I-1]) {
for (int i=I+1;i<n;++i) {
if (s[i] != s[I]) {
ans.push_back({I, i});
for (int j=I;j<=i;++j) s[j] = '1' + '0' - s[j];
break;
}
}
}
if (s[I] == s[I-1]) {
for (int i=I-2;i>=0;--i) {
if (s[i] != s[I-1]) {
ans.push_back({i, I-1});
for (int j=i;j<I;++j) s[j] = '1' + '0' - s[j];
break;
}
}
}
assert(s[I-1] != s[I]);
int swapped = 0;
for (int j=n-1;j>I;--j) {
if (swapped) s[j] = '1' + '0' - s[j];
if (s[j] != t[j]) {
swapped ^= 1;
ans.push_back({I-1, j});
s[j] = t[j];
}
}
if (swapped) {
s[I-1] = '1' + '0' - s[I-1];
s[I] = '1' + '0' - s[I];
swapped = 0;
}
for (int j=0;j<I-1;++j) {
if (swapped) s[j] = '1' + '0' - s[j];
if (s[j] != t[j]) {
swapped ^= 1;
ans.push_back({j, I});
s[j] = t[j];
}
}
if (swapped) {
s[I-1] = '1' + '0' - s[I-1];
s[I] = '1' + '0' - s[I];
swapped = 0;
}
if (s[I] != t[I]) {
ans.push_back({I-1, I});
s[I-1] = '1' + '0' - s[I-1];
s[I] = '1' + '0' - s[I];
}
for (int i=0;i<n;++i) assert(s[i] == t[i]);
cout << ans.size() << '\n';
assert((int)ans.size() <= n);
for (auto &e : ans) cout << e[0] + 1 << " " << e[1] + 1 << '\n';
}
int main() {
int T = readIntLn(1, TMAX);
while (T--) {
solve();
}
assert(sum_n <= SUM_N);
// assert(getchar() == EOF);
cerr << fixed << setprecision(10);
cerr << (clock() - start) / ((long double)CLOCKS_PER_SEC) << " secs\n";
return 0;
}