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
#include <algorithm>
#include <string>
#include <message.h>
#include <vector>
#include <cstdio>
#include <cstring>

//#include "log.h"
//using logging::info;

#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i,p,k) for(int i=(p); i<=(k); ++i)

template<typename T> inline void checkmin(T &a, T b){ if(b<a) a = b; }
template<typename T> inline void checkmax(T &a, T b){ if(a<b) a = b; }

enum { n_max = 110000, msg = 980, chunk = n_max/msg };


struct Val
{
  int d,x;
  Val operator+(int v) const { return Val{d+v,x}; }
  Val chg(char a, char b) const
  { return a==b ? *this : Val{d+1,x+(a<b)}; }
  bool operator<(const Val &b) const { return d!=b.d?d<b.d:x<b.x; }
};

char a[n_max],b[n_max];
Val D[2][n_max];

int main()
{
  int asize,bsize;
  scanf("%d%d %s %s",&asize,&bsize,a,b);

  int N = NumberOfNodes();
  int I = MyNodeId();
  int b0 = I*bsize/N;
  int b1 = (I+1)*bsize/N;
  
  int bs = b1-b0+1;
  REP(i,bs) D[0][i] = Val{b0+i,0};
  bool cur = 1;
  
  //info("range [%;%]",b0,b1);
  REP(ai,asize)
  {
    if(I)
    {
      if(!(ai%chunk)) Receive(I-1);
      D[cur][0].d = GetInt(I-1);
      D[cur][0].x = GetInt(I-1);
    } else D[cur][0] = Val{ai+1,0};
    FOR(i,1,bs-1)
    {
      D[cur][i] = std::min(D[!cur][i],D[cur][i-1])+1;
      checkmin(D[cur][i],D[!cur][i-1].chg(a[ai],b[b0+i-1]));
    }
    if(I<N-1)
    {
      PutInt(I+1,D[cur][bs-1].d);
      PutInt(I+1,D[cur][bs-1].x);
      if(!((ai+1)%chunk) || ai==asize-1) Send(I+1);
    }
    cur = !cur;
  }
  if(I==N-1) printf("%d %d\n",D[!cur][bs-1].d,D[!cur][bs-1].x);

  return 0;
}