I was trying to solve this problem but was running out of time on testcases 10 and 20, so I decided to try the offical solution here but this one also was running out of time. Is there something that Im missing?
In these two testcases you need to output an insane amount of data (more than 7mb on a textfile), and that’s probably what is making both solutions fail.
Oh no, I guess it is a difference in the Python version between the judging environment used for testing vs the one actually used by contestants.
Anyway, I would suggest using C++ instead.
I used c++ on my solution (it isn’t outputting a correct solution when p = 2 and when p = 3), on all other testcases it’s pretty fast.
Here’s my code:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x) for (int i = 0; i < (x); i++)
#define reps(i,j,x) for(int i=(j);i<(x);i++)
void print(){cout<<endl;} template <typename T, typename... Types> void print(T var1, Types... var2) {cout<<var1<<" ";print(var2...);}
void solve();
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("snakes.in", "r", stdin);
#endif
// freopen("snakes.out", "w", stdout);
cout << fixed << setprecision(15);
int t=1;
cin>>t;
rep(i,t){
solve();
}
}
void solve(){
int n,p;
cin>>n>>p;
string st[2];
cin>>st[0]>>st[1];
int c[2]={1,1};
rep(j,2)reps(i,1,n){
c[j]+=st[j][i]!=st[j][i-1];
}
int diff = st[0][0]!=st[1][0],nbacker = (c[0] + c[1] <=3);
print(c[0]+c[1] - diff - nbacker);
if(p==1)return;
int one=0,two=1;
if(diff)if((st[0][0]!='1'))swap(one,two);
if(!diff && st[0][n-1]!=st[1][n-1]){
if(st[0][n-1]=='1')swap(one,two);
}
if(nbacker){
if(c[0]>c[1])print(1,2);
else print(2,1);
return;
}
int lastone=st[one][n-1]=='2',lasttwo=st[two][n-1]=='2';
int backer;
if(st[0][n-1]==st[1][n-1]){
if(c[one]>1){
c[one]--;
print(one+1,two+1);
lastone=(lastone+1)%2;
}
else{
c[two]--;
print(two+1,one+1);
lasttwo=(lasttwo+1)%2;
}
}
bool first = true;
while(c[one]>(0 + st[one][0]=='1')){
if(first){
first=false;
backer=lastone;
}
if(backer==lastone)print(one+1,3);
else print(one+1,two+1);
lastone=(lastone+1)%2;
c[one]--;
}
while(c[two]>(0 + st[two][0]=='2')){
if(backer==lasttwo)print(two+1,3);
else print(two+1,one+1);
c[two]--;
lasttwo=(lasttwo+1)%2;
}
print(3, backer==0 ? one+1 : two+1);
}
You are right, thank you.
(I know that but I forgot that I used that in print sorry, I want to flush the output for debugging)
I also noticed one strange behavior (I don’t know if I should open another post for this but it’s for the same problem): on inputs 11 and 21 my code outputs the same exact code as the one of the solution and the one in the solutions, but it still count it as wrong (I already checked and I don’t print extra space at the end of each line, the output of the programs are exactly the same characters)
my code:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x) for (int i = 0; i < (x); i++)
#define reps(i,j,x) for(int i=(j);i<(x);i++)
void solve();
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("snakes.in", "r", stdin);
#endif
// freopen("snakes.out", "w", stdout);
cout << fixed << setprecision(15);
int t=1;
cin>>t;
rep(i,t){
solve();
}
}
void solve(){
int n,p;
cin>>n>>p;
string st[2];
cin>>st[0]>>st[1];
int c[2]={1,1};
rep(j,2)reps(i,1,n){
c[j]+=st[j][i]!=st[j][i-1];
}
int diff = st[0][0]!=st[1][0],nbacker = (c[0] + c[1] <=3);
cout<<(c[0]+c[1] - diff - nbacker)<<'\n';
if(p==1)return;
int one=0,two=1;
if(diff)if((st[0][0]!='1'))swap(one,two);
if(!diff && st[0][n-1]!=st[1][n-1]){
if(st[0][n-1]=='1')swap(one,two);
}
if(nbacker){
if(c[0]>c[1])cout<<1<<" "<<2<<'\n';
else cout<<2<<" "<<1<<'\n';
return;
}
int lastone=st[one][n-1]=='2',lasttwo=st[two][n-1]=='2';
int backer;
if(st[0][n-1]==st[1][n-1]){
if(c[one]>1){
c[one]--;
cout<<one+1<<" "<<two+1<<'\n';
lastone=(lastone+1)%2;
}
else{
c[two]--;
cout<<two+1<<" "<<one+1<<'\n';
lasttwo=(lasttwo+1)%2;
}
}
bool first = true;
while(c[one]>(0 + st[one][0]=='1')){
if(first){
first=false;
backer=lastone;
}
if(backer==lastone)cout<<one+1<<" "<<3<<'\n';
else cout<<one+1<<" "<<two+1<<'\n';
lastone=(lastone+1)%2;
c[one]--;
}
while(c[two]>(0 + st[two][0]=='2')){
if(backer==lasttwo)cout<<two+1<<" "<<3<<'\n';
else cout<<two+1<<" "<<one+1<<'\n';
c[two]--;
lasttwo=(lasttwo+1)%2;
}
cout<<3<<" "<<( backer==0 ? one+1 : two+1)<<'\n';
}
21.in:
10
4 3
1111
2121
4 3
2121
1111
4 3
1111
2121
4 3
2121
1111
4 3
1111
2121
4 3
2121
1111
4 3
1111
2121
4 3
2121
1111
4 3
1111
2121
4 3
2121
1111
21.out / my output / official solution’s output:
4
2 1
2 3
2 1
3 2
4
1 2
1 3
1 2
3 1
4
2 1
2 3
2 1
3 2
4
1 2
1 3
1 2
3 1
4
2 1
2 3
2 1
3 2
4
1 2
1 3
1 2
3 1
4
2 1
2 3
2 1
3 2
4
1 2
1 3
1 2
3 1
4
2 1
2 3
2 1
3 2
4
1 2
1 3
1 2
3 1
I tried running your solution and it does not output what you’ve sent above:
Btw, the Python code runs fast enough if everything is concatenated before being printed:
import sys
def to_reduced_list(s):
"""Compress runs of equal chars in a string s, and converts to int
>>> to_reduced_list('2211')
[2, 1]
"""
l = []
for c in s:
c = int(c)
if len(l) > 0 and l[-1] == c:
continue
l.append(c)
return l
output = []
def solve():
N, P = map(int, input().split())
tubes = [to_reduced_list(input()) for _ in range(2)]
tubes.append([])
if tubes[0][0] == tubes[1][0]: # ensure f and s start with different chars
tubes[0].insert(0, tubes[0][0] ^ 3)
ans = len(tubes[0]) + len(tubes[1]) - 2
if ans > 1:
ans += 1
output.append(f"{ans}")
if P == 1:
return
moves = []
def move(src, dst):
moves.append((src, dst))
if len(tubes[dst]) == 0 or tubes[dst][-1] != tubes[src][-1]:
tubes[dst].append(tubes[src][-1])
tubes[src].pop()
if tubes[0][-1] == tubes[1][-1]: # step 1: if equal last chars
if len(tubes[0]) > len(tubes[1]):
move(0, 1)
else:
move(1, 0)
for i in range(2):
if len(tubes[i]) > 1:
move(i, 2) # step 2: move from any tube with string length > 1 to beaker
idx_to_empty = 0 # step 3: choose a tube to (almost) empty first
if tubes[idx_to_empty][0] == tubes[2][0]:
idx_to_empty ^= 1
while len(tubes[idx_to_empty]) > 1:
if tubes[idx_to_empty][-1] == tubes[2][0]:
move(idx_to_empty, 2)
else:
move(idx_to_empty, idx_to_empty ^ 1)
idx_to_empty ^= 1 # step 4: next, (almost) empty the other tube
while len(tubes[idx_to_empty]) > 1:
if tubes[idx_to_empty][-1] == tubes[2][0]:
move(idx_to_empty, 2)
else:
move(idx_to_empty, idx_to_empty ^ 1)
move(2, idx_to_empty) # step 5: finish
break
assert len(moves) == ans
for a, b in moves:
output.append(f"{1 + a} {1 + b}")
T = int(input())
for _ in range(T):
solve()
print("\n".join(output))thank you, the fault was of one variable not initialized on some cases.