codeforces 950 #469 div2 D A Leapfrog in the Array

Problem

codeforces.com/contest/950/problem/D

Reference

Codeforces Round #469 (Div. 2) D. A Leapfrog in the Array (思维）

Meaning

开始时将 n 个数 1 ~ n 放在一个数组里，数 i 放在下标为 $2i-1$ 的格（下标从 1 开始）。
然后进行移动操作，每次把最右边的数放到它左边离它最近的空格中，直到 n 个数都在前 n 个格中为止。
有 q 个循问，每次给出下标 x，问这个格里装的数是几。

Analysis

考虑算出这个下标的数在移动前的下标。
可以看出，移动前数是隔一个位隔一个位放的，都处于奇数下标位置。
移动的效果就是将后面的 $\lfloor\frac{n}{2}\rfloor$ 个数填满前面的空格，而原来的前 $\lceil\frac{n}{2}\rceil$ 个数是不会动的。
所以，在移动后，在奇数位的数还是原来的数，即下标没变；
对于在偶数下标 x 的数，这时在它左边有 $\lfloor\frac{x}{2}\rfloor$ 个奇数位，它们是没变过的，即它刚跳到这个位置时左边就有 $\lfloor\frac{x}{2}\rfloor$ 个数，而在它右边则有 $n-\lfloor\frac{x}{2}\rfloor$ 个数，所以在这一跳之前它的下标应为 $x'=x+(n-\lfloor\frac{x}{2}\rfloor)$。若 $x'$ 还是偶数下标，分析类似。

Code

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long n, x;
    int q;
    cin >> n >> q;
    while(q--)
    {
        cin >> x;
        while(~x & 1)
            x += n - x / 2;
        cout << (x + 1 >> 1) << '\n';
    }
    return 0;
}