洛谷 P1563 玩具谜题

// P1563 的第 ① 版：老老实实一步一步走
//
// 「向左数第 s 个」就真的走 s 步，每一步问一次「现在这个人朝哪边」—— 题意的逐字翻译，
// 而且**它是对的**：走一步和一次走 s 步，落点完全一样（朝向只看出发的那个人）。
//
// ⚠ 它只是慢：n, m <= 1e5，而 s 可以到 n - 1 ⇒ 最坏要走 m * (n-1) ≈ 10^10 步。
//   正文第 ④ 步有秒表：本机 n = m = 1e5 的最坏数据要跑十几秒，题目限时 1 秒。
//
// ★ 这一版仍然值得写出来：它是标准答案，也是对拍里那一栏「一定对」的东西。

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

int main() {
    ios::sync_with_stdio(false);          // 1e5 行输入，关掉同步（第 45 章量过）
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> dir(n);
    vector<string> job(n);
    for (int i = 0; i < n; i++) cin >> dir[i] >> job[i];
    int cur = 0;
    for (int i = 0; i < m; i++) {
        int a, s;
        cin >> a >> s;
        int step = (dir[cur] == a) ? -1 : 1;      // 方向只由**出发的那个人**决定
        for (int k = 0; k < s; k++) cur = (cur + step + n) % n;   // 一步一步挪
    }
    cout << job[cur] << '\n';
    return 0;
}

// P1563 的错法演示：忘了「C++ 的 % 对负数给负余数」
//
//     cur = (cur - s) % n;      // ⚠ cur 变成负数，下标就飞出去了
//
// ★ 为什么这份用 job.at(cur) 而不是 job[cur]（第 45 章那一课）：
//   `job[cur]` 在 cur 为负时是**未定义行为** —— 它可能崩、可能打出一串乱码、
//   也可能在 -O2 下被优化成别的样子，**每台机器给的结果都不一样，教材写不了**。
//   换成 .at() 就变成一个确定的 std::out_of_range，谁跑都一样。
//
// ⇒ 演示错误写法时，要把那个错**钉成可复现的**，不能留给 UB 去发挥。
//
// ⚠ 另一条（做这一页时量出来的）：**一次「崩溃退出」在本机要 1.17 秒**
//   （abort 走的是 core dump 那条路），而正常跑完只要几毫秒。
//   所以这一版只在样例上跑一次，**不进 300 轮对拍表** —— 那会让 check:viz 多花六分钟。

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

int main() {
    ios::sync_with_stdio(false);          // 1e5 行输入，关掉同步（第 45 章量过）
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> dir(n);
    vector<string> job(n);
    for (int i = 0; i < n; i++) cin >> dir[i] >> job[i];
    int cur = 0;
    for (int i = 0; i < m; i++) {
        int a, s;
        cin >> a >> s;
        cur = (dir.at((size_t)cur) == a) ? cur - s : cur + s;
        cur = cur % n;                        // ⚠ 少了 + n：-3 % 7 还是 -3
    }
    cout << job.at((size_t)cur) << '\n';
    return 0;
}

// 把「负数取模」摊开看：同一组指令，两种写法的下标逐步对照
//
// 用法：./p1563Trace          跑样例 1（7 个人 3 条指令）
//       ./p1563Trace csv      只打 `键,值`，给 check:viz 用
//
// ★ 看第一步就够了：`0 - 3 = -3`，而 C++ 的 `-3 % 7` 给的是 **-3**，不是 4。
//   下标一旦为负，`vector` 一访问就飞 —— 而**样例的第一条指令就会踩到它**。

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

int main(int argc, char** argv) {
    bool csv = (argc > 1 && string(argv[1]) == "csv");
    const int n = 7;
    int dir[7] = {0, 0, 0, 1, 1, 0, 1};
    const char* job[7] = {"singer", "reader", "mengbier", "thinker",
                          "archer", "writer", "mogician"};
    int cmd[3][2] = {{0, 3}, {1, 1}, {0, 2}};

    int cur = 0;
    int badAt = 0, badIdx = 0;           // 只写 % n 的那版：第几步出界、出界成了几
    if (!csv) printf("步  指令      算出来  正确 (cur %% n + n) %% n   只写 cur %% n\n");
    for (int i = 0; i < 3; i++) {
        int a = cmd[i][0], s = cmd[i][1];
        int raw = (dir[cur] == a) ? cur - s : cur + s;
        int good = (raw % n + n) % n;
        int bad = raw % n;
        if (!badAt && bad < 0) { badAt = i + 1; badIdx = bad; }
        if (!csv)
            printf("%d   %s %d      %3d     %d (%s)          %d%s\n", i + 1,
                   a == 0 ? "左数" : "右数", s, raw, good, job[good], bad,
                   bad < 0 ? "   <- 负下标！" : "");
        cur = good;                       // ★ 往下走的是正确的那一支
    }
    if (csv) {
        printf("answer,%s\nbadAt,%d\nbadIdx,%d\n", job[cur], badAt, badIdx);
    } else {
        printf("\n正确写法落在 %d 号（%s）—— 正是样例的答案\n", cur, job[cur]);
        printf("只写 %% n 的那版：第 %d 步就成了 %d —— vector 一访问就飞\n", badAt, badIdx);
    }
    return 0;
}

// P1563 玩具谜题（NOIP 2016 提高组 D1T1）—— 能 AC 的那一版
//
// 输入是**按逆时针顺序**给的，所以下标 +1 就是逆时针、-1 就是顺时针。
// 于是四种情况可以摆成一张表（0 = 朝内 / 朝外，a = 0 左数 / 1 右数）：
//
//   朝内(0) 左数(0)  ->  左边是顺时针  ->  -s
//   朝内(0) 右数(1)  ->  右边是逆时针  ->  +s
//   朝外(1) 左数(0)  ->  左边是逆时针  ->  +s
//   朝外(1) 右数(1)  ->  右边是顺时针  ->  -s
//
// ★ 盯着这张表看十秒：**朝向和方向一样就往回走，不一样就往前走** —— 一句 dir == a 就够了。
//   四个 if 抄错一个就全错，而这一句压根没有可抄错的地方。
//
// ⚠ C++ 的 % 对负数给的是负余数（-3 % 7 == -3），所以要 (x % n + n) % n。
//   这里 s < n，减完最小是 -(n-1)，一句 + n 就够了。

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

int main() {
    ios::sync_with_stdio(false);          // 1e5 行输入，关掉同步（第 45 章量过）
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> dir(n);
    vector<string> job(n);
    for (int i = 0; i < n; i++) cin >> dir[i] >> job[i];
    int cur = 0;
    for (int i = 0; i < m; i++) {
        int a, s;
        cin >> a >> s;
        cur = (dir[cur] == a) ? cur - s : cur + s;    // ★ 一句话代替四个 if
        cur = (cur % n + n) % n;                      // ⚠ 负数取模
    }
    cout << job[cur] << '\n';
    return 0;
}