13442-Luckymoney2

 avatar
unknown
c_cpp
2 years ago
1.9 kB
5
Indexable
#include <stdio.h>
#include <stdlib.h>

typedef struct _Node
{
    int number, age;
    struct _Node *prev;
    struct _Node *next;
} Node;

int cmp(const void *a, const void *b);
Node *head;
Node *coin_arr[5000001];
Node *createList(int n);
Node *solve(int n, int m);

Node *createList(int n)
{
    Node *list = malloc(n * sizeof(Node));
    for (int i = 0; i < n; ++i)
    {
        list[i].number = i + 1;
        scanf("%d", &list[i].age);
        coin_arr[i] = &list[i];

        if (i != n - 1)
            list[i].next = &list[i + 1];
        else
            list[i].next = &list[0];

        if (i != 0)
            list[i].prev = &list[i - 1];
        else
            list[i].prev = &list[n - 1];
    }

    qsort(coin_arr, n, sizeof(coin_arr[0]), cmp);

    return list;
}

Node *solve(int n, int m)
{
    for (int i = 0; i < m; ++i)
    {
        int a, k;
        char dir;
        scanf("%d %d %c", &a, &k, &dir);
        k = k % (n - 1); //here i am confused
        if (k == 0)
            continue;

        Node *cur = coin_arr[a - 1];
        Node *next = coin_arr[a - 1]->next;
        Node *prev = coin_arr[a - 1]->prev;

        prev->next = next;
        next->prev = prev;

        if (dir == 'R')
        {
            while (k--)
            {
                prev = prev->next;
                next = next->next;
            }
        }
        else if (dir == 'L')
        {
            while (k--)
            {
                prev = prev->prev;
                next = next->prev;
            }
        }

        cur->prev = prev;
        cur->next = next;
        prev->next = cur;
        next->prev = cur;
    }

    return coin_arr[0]; //here i am confused
}

int cmp(const void *a, const void *b)
{
    Node *i = *(Node **)a;
    Node *j = *(Node **)b;
    if (i->age != j->age)
        return i->age - j->age;
    else
        return i->number - j->number;
}
Editor is loading...