Codeforces 950D(模拟)

Codeforces 950D
题意：最开始$n$个数字中的数字$i$在位置$2 \cdot i-1$，之后从右向左依次用数字将该列填充。最后$q$个$query$问你$pos$为$x_i$该填上什么数字。

可以发现奇数位的数字不会改变，然后只需要考虑偶数位是哪里移过来的。
考虑还原，当偶数位$x$的数被移动时，它的右边一定有$x / 2$个未移动的数，所以是从$x+x/2$移动过来的
如果当前还原操作位置已经是奇数，输出$(x+1)/2$

Codeforces Submission

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define pr pair<int, int>
#define fir first
#define sec second
#define mp make_pair
LL n, q;
void clean() {
}
int solve() {
    clean();
    while (q--) {
        LL x; 
        cin >> x;
        while (1) {
            if (x & 1) {
                cout << (x + 1) / 2 << endl;
                break;
            }
            x += n - x / 2;
        }
    }
    return 0;
}
int main() {
    cin >> n >> q, solve();
    return 0;
}