ZeroJudge F581: Ring Exit

There are n rooms arranged in a circle, numbered from 0 to n-1.

There are one-way paths between the rooms, allowing room i to reach room (i+1) % n.

Every time you enter room i, you can earn p_i points (you can also earn points from the room you start in).

Now there are m tasks in order, and the i-th task requires collecting q_i points. For each task, if you start in room s and reach room t while collecting the required points, you will end up in room (t+1) % n after completing the task.

You start in room 0. Based on the m tasks received, determine which room you will be in after completing the m-th task.

Sample Inputs/Outputs

Thought Process

Use binary search, but change the target to Q_i plus the prefix sum at the current position, and take the result modulo N. If the target exceeds the maximum prefix sum (the last number), subtract the maximum prefix sum from the target. Finally, output the final position.

Sample Code－ZeroJudge F581: Ring Exit

#include <iostream>
using namespace std;

int N, M, num[200000] = {}, prefix[200000] = {};

int binary(const int L, const int R, const int target) {
    if (L >= R) return R;
    const int middle = (L+R)/2;
    if (target > prefix[middle]) {
        return binary(middle+1, R, target);
    }
    return binary(L, middle, target);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    int sum = 0;
    prefix[0] = 0;
    for (int i = 0; i<N; i++) {
        cin >> num[i];
        sum += num[i];
        prefix[i+1] = sum;
    }
    int position = 0;
    for (int i = 0; i<M; i++) {
        int Q;
        cin >> Q;
        int target = Q+prefix[position];
        if (target > prefix[N]) target -= prefix[N];
        position = binary(0, N, target) % N;
    }
    cout << position << "\n";
}

//ZeroJudge F581
//Dr. SeanXD