1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
#include "message.h"

#define FWD(a,b,c) for(int a=(b); a<(c); ++a)
#define st first
#define nd second
#define ALL(c) (c).begin(), (c).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int INF = 1000010;

inline PII operator+(const PII &a, const PII &b){
	return PII(a.st + b.st, a.nd + b.nd);
}

int u, us;
int n, m;
char S[130000];
char T[130000];

void sendOne(int w, int i, int j, char side, vector<PII> V){
	PutInt(w, i);
	PutInt(w, j);
	PutChar(w, side);
	for(PII v : V){
		PutInt(w, v.st);
		PutInt(w, v.nd);
	}
	Send(w);
}

int main(){
	u = MyNodeId();	
	us = NumberOfNodes();
	scanf("%d %d", &n, &m);
	scanf("%s %s", S, T);
	int r = 2*us;
	int p = (n+r-1)/r;
	int q = (m+r-1)/r;
	int who[r][r];
	vector<PII> mine;
	vector<PII> left[r][r];
	vector<PII> top[r][r];
	int c = 0;
	bool fin = 0;
	bool needed[r][r];
	FWD(s,0,r+r-1){
		FWD(i,max(0,s-r+1),min(r-1,s)+1){
			int j = s-i;
			who[i][j] = c;
			if(!fin && c == u) mine.push_back(PII(i,j));
			needed[i][j] = !fin;
			if(i*p <= n-1 && n-1 < i*p+p && j*q <= m-1 && m-1 < j*q+q) fin = 1;
			c = (c+1) % us;
		}
	}
	for(PII kw : mine){
		int i = kw.st;
		int j = kw.nd;
		int x = i * p;
		int y = j * q;
		if(i == 0) FWD(k,0,q+1) top[i][j].push_back(PII(y+k, 0));
		if(j == 0) FWD(k,0,p+1) left[i][j].push_back(PII(x+k, 0));
		while(top[i][j].empty() || left[i][j].empty()){
			int source = Receive(-1);
			int i = GetInt(source);
			int j = GetInt(source);
			char side = GetChar(source);
			if(side == 0)
				FWD(k,0,p+1){
					int a = GetInt(source);
					int b = GetInt(source);
					left[i][j].push_back(PII(a, b));
				}
			else
				FWD(k,0,q+1){
					int a = GetInt(source);
					int b = GetInt(source);
					top[i][j].push_back(PII(a, b));
				}
		}
		vector<PII> bot, right;
		PII W[2][q+1];
		bot.push_back(left[i][j].back());
		right.push_back(top[i][j].back());
		FWD(b,0,q+1) W[0][b] = top[i][j][b];
		FWD(a,1,min(p,n-x)+1){
			W[a&1][0] = left[i][j][a];
			FWD(b,1,min(q,m-y)+1){
				PII le = W[a&1][b-1] + PII(1, 0);
				PII to = W[1-(a&1)][b] + PII(1, 0);
				PII di = W[1-(a&1)][b-1] + PII((S[x+a-1] == T[y+b-1] ? 0 : 1), S[x+a-1] < T[y+b-1] ? 1 : 0);
				W[a&1][b] = min(min(le,to),di);
				if(x+a == n && y+b == m) printf("%d %d\n", W[a&1][b].st, W[a&1][b].nd);
			}
			right.push_back(W[a&1][q]);
		}
		FWD(b,1,q+1) bot.push_back(W[p&1][b]);
		bot.resize(q+1);
		right.resize(p+1);
		if(i != r-1 && needed[i+1][j]) sendOne(who[i+1][j], i+1, j, 1, bot);		
		if(j != r-1 && needed[i][j+1]) sendOne(who[i][j+1], i, j+1, 0, right);
	}
	return 0;
}