Untitled

mail@pastecode.io avatar
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;
}