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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include "message.h"
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <cassert>

#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(u) (u).begin(),(u).end()

using namespace std;

typedef pair<int,int> PII;

ostream & operator<<(ostream & out, vector<int> V) {
    out << "[";
    for(auto v : V) out << v << ", ";
    out << "]";
    return out;
}

int ceildiv(int a, int b) {
    return (a + b - 1) / b;
}

const int MAXN = 200000;
char up_str[MAXN], left_str[MAXN];

void send_vector(int dst, vector<PII>& V) {
    PutInt(dst, V.size());
    for (PII ab : V) {
        PutInt(dst, ab.first);
        PutInt(dst, ab.second);
    }
    Send(dst);
}

void read_vector(int from, vector<PII>& V) {
    assert(from == Receive(from));
    int count = GetInt(from);
    V.resize(count);
    REP(i, count) {
        V[i].first = GetInt(from);
        V[i].second = GetInt(from);
    }
}

int w, h, mat_rows, mat_cols, my_id, nodes, width, height;

vector<PII> from_up[2];
vector<PII> from_left, to_right;

PII inc_first(PII a) {
    return make_pair(a.first + 1, a.second);
}

PII inc_second(PII a) {
    return make_pair(a.first, a.second + 1);
}

void solve(int row, int col) {
    //printf("%d: (%d %d) start\n", my_id, row, col);
    if (row == 0) {
        from_up[0].resize(1 + min(w, width - col*w));
        for(int i = 0; i < 1 + width - col*w and i < 1 + w; i++) {
            from_up[0][i] = PII(col * w + i, 0);
        }
    }
    if (col == 0) {
        from_left.resize(1 + min(h, height - row*h));
        for(int i = 0; i < 1 + height - row * h and i < 1 + h; i++) {
            from_left[i] = PII(row * h + i, 0);
        }
    } else {
        int prev_node = (my_id + nodes - 1) % nodes;
        read_vector(prev_node, from_left);
    }
    from_up[1].resize(from_up[0].size());
    to_right.resize(from_left.size());
    assert(from_up[0][0] == from_left[0]);
    to_right[0] = from_up[0].back();
    int src = 0;
    //printf("%d: (%d %d) ready\n", my_id, row, col);
    for(int r = 1; r <= height - row * h and r <= h; r++) {
        int dst = 1 - src;
        from_up[dst][0] = from_left[r];
        for(int c = 1; c <= width - col * w and c <= w; c++) {
            int pos_up = col * w + c - 1;
            int pos_left = row * h + r - 1;
            if (up_str[pos_up] == left_str[pos_left]) {
                from_up[dst][c] = from_up[src][c-1];
            } else if (up_str[pos_up] > left_str[pos_left]) { //TODO : upewnij sie, ze up jest zrodlem
                from_up[dst][c] = inc_first(min(from_up[src][c-1], min(from_up[src][c], from_up[dst][c-1])));
            } else {
                from_up[dst][c] = inc_first(min(inc_second(from_up[src][c-1]), min(from_up[src][c], from_up[dst][c-1])));
            }
        }
        to_right[r] = from_up[dst].back();
        src = dst;
    }
    //printf("%d: (%d %d) calculated\n", my_id, row, col);
    if (col + 1 < mat_cols) {
        int next_node = (my_id + nodes + 1) % nodes;
        send_vector(next_node, to_right);
        //printf("%d: (%d %d) sending\n", my_id, row, col);
    }
    from_up[0] = from_up[src];
    if (col + 1 == mat_cols and row + 1 == mat_rows) {
        printf("%d %d\n", from_up[0].back().first, from_up[0].back().second);
    }
    //printf("%d: (%d %d) done\n", my_id, row, col);
}

int main() {
    int n, m;
    scanf("%d %d", &width, &height);
    scanf("%s %s", up_str, left_str);
    // TODO : czy zamienic start z end?
    // TODO : dobrac h vs w
    nodes = NumberOfNodes();
    my_id = MyNodeId();
    w = ceildiv(width, nodes);
    h = ceildiv(height, 900);
    mat_rows = ceildiv(height, h);
    mat_cols = ceildiv(width, w);
    for (int col = my_id; col < mat_cols; col += nodes) {
        for (int row = 0; row < mat_rows; row++) {
            solve(row, col);
        }
    }
    //printf("%d exiting\n", my_id);
    return 0;
}