#include #include #define LIST_MAX_SUBLIST_COUNT 80 #define SUBLIST_MAX_ELEMENTS_COUNT 400 class SubList; class List{ public: List* prev; List* next; SubList* subList; int elementsCount; List(){ prev = NULL; next = NULL; subList = NULL; elementsCount = 0; } }; class SubList{ public: SubList* prev; SubList* next; List* list; std::vector elements; int nextElementsCount; SubList(List* parentList){ prev = NULL; next = NULL; list = parentList; nextElementsCount = 0; } void updateElementsCount(int count, SubList* changedSubList){ if(this != changedSubList) nextElementsCount += count; if(prev){ prev->updateElementsCount(count, changedSubList); } else{ list->elementsCount += count; } } }; int main(int ac, char** av){ unsigned int totalElementsCount = 0, rounds = 0, value = 0, nextMove = 0, currentElementValue = 0; int sublistsInCurrentList = 0, position = 0, positionFirst = 0; List *list = NULL, *firstList = NULL, *tmpList = NULL; SubList *subList = NULL, *tmpSublist = NULL; fscanf(stdin, "%d", &rounds); list = new List(); subList = new SubList(list); list->subList = subList; firstList = list; while(!feof(stdin)){ while(!feof(stdin) && sublistsInCurrentList < LIST_MAX_SUBLIST_COUNT){ while(!feof(stdin) && subList->elements.size() < SUBLIST_MAX_ELEMENTS_COUNT){ fscanf(stdin, "%d", &value); subList->elements.push_back(value); ++totalElementsCount; } ++sublistsInCurrentList; subList->updateElementsCount(subList->elements.size(), subList); if(!feof(stdin) && sublistsInCurrentList < LIST_MAX_SUBLIST_COUNT){ tmpSublist = new SubList(list); subList->next = tmpSublist; tmpSublist->prev = subList; subList = tmpSublist; } } if(!feof(stdin)){ sublistsInCurrentList = 0; tmpList = new List(); list->next = tmpList; tmpList->prev = list; list = tmpList; subList = new SubList(list); list->subList = subList; } } list->next = firstList; firstList->prev = list; list = firstList; subList = list->subList; currentElementValue = subList->elements[position]; for(int runda = 0; runda < rounds; ++runda){ if(currentElementValue % 2 == 0){ // op. R // calculate next element position SubList* subListNext = subList; int nextPosition = position; if(nextPosition+1 < subList->elements.size()){ nextPosition += 1; } else if(subList->next){ subListNext = subList->next; nextPosition = 0; } else { tmpList = subListNext->list->next; while(!tmpList->subList){ tmpList = tmpList->next; } subListNext = tmpList->subList; nextPosition = 0; } nextMove = subListNext->elements[nextPosition]; // remove next element subListNext->elements.erase(subListNext->elements.begin() + nextPosition); subListNext->updateElementsCount(-1, subListNext); if(subListNext->elements.size() == 0){ if(subListNext->prev == NULL){ // first sublist of list if(subListNext->next){ // not last sublist of list, replace sublist of list with next sublist subListNext->list->subList = subListNext->next; subListNext->next->prev = NULL; } else{ // last sublist of list, list is empty, remove list subListNext->list->prev->next = subListNext->list->next; subListNext->list->next->prev = subListNext->list->prev; } } else{ // not first sublist of list subListNext->prev->next = subListNext->next; if(subListNext->next) subListNext->next->prev = subListNext->prev; } } if(subListNext == subList && nextPosition < position){ position -= 1; } --totalElementsCount; } else{ // op. X nextMove = currentElementValue; // add new element subList->elements.insert(subList->elements.begin()+position+1, nextMove - 1); subList->updateElementsCount(1, subList); ++totalElementsCount; } // move to next element if(totalElementsCount > 0){ nextMove = nextMove % totalElementsCount; if(subList->elements.size() > position + nextMove){ // same SubList position = position + nextMove; } else if(subList->elements.size() + subList->nextElementsCount > nextMove + position){ // same List nextMove -= subList->elements.size() - position; position = 0; subList = subList->next; while(nextMove >= subList->elements.size()){ nextMove -= subList->elements.size(); subList = subList->next; } position = nextMove; } else{ // other List nextMove -= subList->nextElementsCount + subList->elements.size() - position; list = list->next; while(nextMove >= list->elementsCount){ nextMove -= list->elementsCount; list = list->next; } subList = list->subList; while(nextMove >= subList->elements.size()){ nextMove -= subList->elements.size(); subList = subList->next; } position = nextMove; } currentElementValue = subList->elements[position]; } else break; } if(totalElementsCount > 0){ // show elements firstList = subList->list; tmpSublist = subList; positionFirst = position; list = firstList; printf("%u", subList->elements[position]); ++position; while(list != firstList || subList != tmpSublist || position != positionFirst){ if(position < subList->elements.size()){ printf(" %u", subList->elements[position]); ++position; } else{ position = 0; if(subList->next) subList = subList->next; else{ list = list->next; subList = list->subList; } } } } else{ printf("-1"); } return 0; }