A0750 [2012J2]寻宝

#include <bits/stdc++.h>
using namespace std;

const int MOD = 20123;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    // x[i][j]：第 i 层 j 号房间指示牌上的数字
    vector<vector<int>> x(N + 1, vector<int>(M));
    // stair[i]：第 i 层有楼梯的房间编号（递增）
    vector<vector<int>> stair(N + 1);

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < M; j++) {
            int has;
            cin >> has >> x[i][j];
            if (has) stair[i].push_back(j);
        }
    }

    int cur;  // 当前进入的房间（从底层开始）
    cin >> cur;

    long long ans = 0;
    for (int i = 1; i <= N; i++) {
        int v = x[i][cur];
        ans = (ans + v) % MOD;   // 本层第一个进入的房间的指示牌数字计入密钥

        const vector<int> &st = stair[i];
        int c = (int)st.size();
        if (c == 0) break;       // 这一层没有楼梯，无法继续往上（数据保证不会出现）

        // 从 cur 开始逆时针遇到的第一个楼梯在 st 中的下标
        int p = (int)(lower_bound(st.begin(), st.end(), cur) - st.begin());
        if (p == c) p = 0;       // cur 之后的环上已无楼梯，绕回 0 号

        // 指示牌写 v：从第一个楼梯再往后数 v-1 个楼梯
        int idx = (p + (v - 1) % c) % c;
        cur = st[idx];           // 从这个楼梯上楼，到达上一层的同号房间
    }

    cout << ans << '\n';
    return 0;
}