Untitled
unknown
c_cpp
2 years ago
2.5 kB
2
Indexable
Never
#include<stdio.h> #include<stdlib.h> #include "function.h" Node* head; int list[500005][2]; int cmp(const void* a, const void* b){ int* aa = (int*)a,* bb = (int*)b; if(aa[0] > bb[0]) return 1; else if(aa[0] == bb[0] && aa[1] > bb[1]) return 1; return -1; } Node* createNode(Node* next, Node* pre, int n){ Node* new = (Node*)malloc(sizeof(Node)); new->age = list[n-1][0]; new->number = n; new->next = next, new->prev = pre; next->prev = new, pre->next = new; return new; } Node* createList(int n){ Node* hhead = (Node*)malloc(sizeof(Node)),* tmp; hhead->prev = hhead->next = hhead, hhead->number = 1; for(int i=0; i<n; i++){ scanf("%d", &list[i][0]); list[i][1] = i+1; } hhead->age = list[0][0]; tmp = hhead; for(int i=2; i<=n; i++) tmp = createNode(hhead, tmp, i); qsort(list, n, 2*sizeof(int), cmp); while(hhead->age != list[0][0]) hhead = hhead->next; // for(int i = 0; i < n; i ++){ // printf("%d ", hhead -> age); // hhead = hhead -> next; // } // puts(""); return hhead; } Node* solve(int n, int m){ Node* node,* des; Node** nodes = (Node**)calloc(n+1, sizeof(Node*)); int a, k, num; char dir; // node = head; // for(int i=1; i<=n; i++){ // nodes[node->number] = node; // node = node->next; // } node = head; while(node->number != 1) node = node->next; for(int i=1; i<=n; i++){ nodes[i] = node; node = node->next; } for(int i=0; i<m; i++){ scanf("%d %d %c", &a, &k, &dir); k = k % (n-1); num = list[a-1][1]; node = nodes[num]; node->prev->next = node->next; node->next->prev = node->prev; des = node; if(dir == 'R'){ while(k--) des = des->next; des->next->prev = node, node->next = des->next; node->prev = des, des->next = node; } else if(dir == 'L'){ while(k--) des = des->prev; des->prev->next = node, node->prev = des->prev; node->next = des, des->prev = node; } // node = head; // for(int i = 0; i < n; i ++){ // printf("%d ", node -> age); // node = node -> next; // } // puts(""); } return head; }