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
#include"message.h"
#include<cstdio>

enum
{
	MAX = 100010,
	MSG_SIZE = 105
};

char txt1[MAX], txt2[MAX];
int _tab[MAX], _tab2[MAX];
int *tab = _tab+1, *prev_tab = _tab2+1;
int _disg[MAX], _disg2[MAX];
int *disg = _disg+1, *prev_disg = _disg2+1;
int min(int a, int b) { return (a<b)?a:b; }

int main()
{
	int n, m; scanf("%d%d", &n, &m);
	scanf("%s",txt1);
	scanf("%s",txt2);

	int instance_id = MyNodeId(), instance_num = min(NumberOfNodes(),m);
	if(instance_id >= instance_num) return 0;
	int y_offset = instance_id*m/instance_num;
	int y_limit = (instance_id+1)*m/instance_num;
	int remaining = 0; int rdy = 0;
	for(int i = 0; i < m; i++)
		tab[i] = i+1;
	for(int i = 0; i < n; i++)
	{
		int *temp = tab; tab = prev_tab; prev_tab = temp;
		temp = disg; disg = prev_disg; prev_disg = temp;
		if(instance_id)
		{
			if(!remaining)
			{
				Receive(instance_id-1);
				remaining = MSG_SIZE;
			}
			tab[y_offset-1] = GetInt(instance_id-1);
			disg[y_offset-1] = GetInt(instance_id-1);
			remaining--;
		}
		else
		{
			tab[y_offset-1] = i+1;
			disg[y_offset-1] = 0;
		}
		for(int j = y_offset; j < y_limit; j++)
		{
			int cost = (txt1[i] == txt2[j])?0:1;
			int candidate = prev_tab[j]+1, disgust = prev_disg[j];
			if(candidate > tab[j-1]+1 || (candidate == tab[j-1]+1 && disgust > disg[j-1]))
				{candidate = tab[j-1]+1; disgust = disg[j-1];}
			int last_c = prev_tab[j-1]+cost;
			int last_d = prev_disg[j-1];
			if(txt1[i] < txt2[j]) last_d++;
			if(candidate > last_c || (candidate == last_c && disgust > last_d))
				{candidate = last_c; disgust = last_d;}
			tab[j] = candidate;
			disg[j] = disgust;
		}
		if(instance_id+1 < instance_num)
		{
			PutInt(instance_id+1,tab[y_limit-1]);
			PutInt(instance_id+1,disg[y_limit-1]);
			rdy++;
			if(rdy >= MSG_SIZE)
			{
				Send(instance_id+1);
				rdy = 0;
			}
		}
	}
	if(rdy)
		Send(instance_id+1);
	if(y_limit == m)
		printf("%d %d\n", tab[m-1], disg[m-1]);

	return 0;
}