EEOJ/OJ4/main.cpp

#include <stdio.h>
#include <vector>
using namespace std;
struct layer{
    unsigned long long int begin;
    unsigned long long int end;
    vector<unsigned int> newDeads;
};
layer layers[135];
int currentLayer = 0;
int layerNum;
int currentDead = 0;
int deadNum, targetNum;
unsigned long long int limit = 4294967295;
unsigned long long int deads[100];
unsigned long long int path[135];
int main(){
    scanf("%d %d", &deadNum, &targetNum);
    for (int i = 0; i < deadNum; i++){
        scanf("%llu", &deads[i]);
    }
long long int prevEnd=1, prevLen=1;
    if(deads[0]!=1){
        layers[0].begin=1;
        layers[0].end=1;
    }
    else{
        layers[0].begin=1;
        layers[0].end=1;
        prevLen=0;
    }
    for (currentLayer = 1; currentLayer < 135; currentLayer++){
        if (prevEnd >= limit || (prevLen == 0&&currentLayer!=0)){
            currentLayer--;
            break;
        }
        layers[currentLayer].begin = prevEnd + 1;
        layers[currentLayer].end = layers[currentLayer].begin + prevLen * 2 - 1;
        if (layers[currentLayer].end > limit){
            layers[currentLayer].end = limit;
            break;
        }
        prevEnd = layers[currentLayer].end;
        prevLen = layers[currentLayer].end - layers[currentLayer].begin + 1;
        for (currentDead=0; currentDead < deadNum; currentDead++){
            if (deads[currentDead] <= layers[currentLayer].end&&deads[currentDead] >= layers[currentLayer].begin){
                prevLen--;
                layers[currentLayer].newDeads.push_back(deads[currentDead]);
            }
        }
    }
    layerNum = currentLayer;
    for (int i = 0; i < targetNum; i++){
        unsigned long long int target;
        scanf("%llu", &target);
        int found=0;
        for (int i = 0; i <= layerNum; i++){
            if (target <= layers[i].end){
                path[i] = target;
                unsigned long long int tmp = target;
                for (int j = i; j > 0; j--){
                    tmp = (tmp - layers[j].begin) / 2 + layers[j - 1].begin;
                    for (auto i = layers[j - 1].newDeads.begin(); i < layers[j - 1].newDeads.end(); i++){
                        if (*i <= tmp){
                            tmp++;
                        }
                        else{
                            break;
                        }
                    }
                    path[j - 1] = tmp;
                }
                for (int t = 0; t <= i; t++){
                    printf("%llu ", path[t]);
                }
                printf("\n");
                found=1;
                break;
            }
        }
        if(!found){
            printf("0\n");
        }
    }
    return 0;
}