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
#include "message.h"
#include <iostream>
#include <cassert>
#include <utility>
using namespace std;
typedef pair<int, int> PII;
const int MAXN = (1<<17)+1;
int n, m;
char src[MAXN];
char tar[MAXN];

PII _best[2][MAXN];
PII *best[2] = {_best[0]+1, _best[1]+1};

inline PII P(PII base, int firstPlus, int secondPlus) {
  return PII(base.first + firstPlus, base.second + secondPlus);
}

int main() {
  assert(4 == scanf("%d%d%s%s", &n, &m, src, tar));
  const int N = NumberOfNodes();
  const int ID = MyNodeId();
  const int len = (n + N - 1) / N;
  const int beg = min(ID * len, n);
  const int end = min((ID + 1) * len, n);
  // cerr << "len: " << len << " beg: " << beg << " end: " << end << endl;

  const int CHUNK = 128;

  /* cerr << "                 ";
  for (int i = 0; i < n; ++i) {
    cerr << "  " << src[i] << "   ";
  }
  cerr << endl;
  */

  for (int i = 0; i < n; ++i) {
    best[1][i] = PII(i+1, 0);
  }

  for (int i = 0; i < m; ++i) {
    int ic = i % 2;
    int ip = (i + 1) % 2;

    if (i % CHUNK == 0) {
      if (ID > 0) {
        Receive(ID - 1);
      }
    }
    PII prev = PII(i+1, 0);
    if (ID > 0) {
      prev.first = GetInt(ID - 1);
      prev.second = GetInt(ID - 1);
    }

    best[ic][beg - 1] = prev;
    // cerr << tar[i] << " best[" << i << "][" << beg << ":" << end << "]: ";
    for (int j = beg; j < end; ++j) {
      PII stay_cost = P(best[ip][j-1], tar[i] != src[j], tar[i] > src[j]);
      best[ic][j] = min(stay_cost,
                    min(P(best[ic][j-1], 1, 0),
                        P(best[ip][j], 1, 0)));
      // cerr << "(" << best[ic][j].first << "," << best[ic][j].second << ") ";
    }
    // cerr << endl;
    if (ID < N - 1) {
      PutInt(ID + 1, best[ic][end - 1].first);
      PutInt(ID + 1, best[ic][end - 1].second);
      if (i == m - 1 or i % CHUNK == CHUNK - 1) {
        Send(ID + 1);
      }
    }
    if (ID == N - 1 and i == m - 1) {
      printf("%d %d\n", best[ic][end - 1].first, best[ic][end - 1].second);
    }
  }

  return 0;
}