카드 배열

카드 배열

문제

하나의 숫자가 쓰여 있는 카드가 N장이 있다. 쓰여 있는 숫자는 0부터 N-1사이의 숫자 중 하나이며, 모든 카드의 숫자는 서로 다르다.

이 카드들 중에서 k개의 카드를 선택하여 배열한 순서를 CK-1, CK-2, ..., C0라고 하자. 

이렇게 배열된 k장의 카드가 N진법의 수를 나타낸다고 하면, 카드 Ci는 N진법의 수에서의 한 자리수를 의미하며 그 자릿수의 값은 Ci×Ni이다.

그러므로 배열된 카드의 수의 값은 Ck-1×Nk-1+Ck-2×Nk-2+...+C0×N0이 된다.

배열되는 카드들 사이에는 Ci＞Cj형태의 제약조건이 주어진다. 제약조건 Ci＞Cj는 Ci숫자가 Cj숫자보다 커야함을 의미한다. 단, i≠j.

예를 들어, N=4, k=3인 경우에 C2＞C0, C0＞C1의 제약조건이 주어졌다고 하자. 

이 경우 가능한 카드의 배열은 (2, 0, 1), (3, 1, 2), (3, 0, 1), 그리고 (3, 0, 2) 네 가지 경우가 있다.

이 네 개의 경우들 중에서 가장 큰 수가 되는 카드의 배열은 (3, 1, 2)이고 이 수의 값은 3×42+1×41+2=54이다. 

또한, 가장 작은 수가 되는 카드 배열은 (2, 0, 1)이고 이 수의 값은 2×42+0×41+1=33이다.

전체 카드의 수와 선택할 카드의 수 그리고 제약조건들이 주어질 때, 

제약조건을 만족하는 카드배열 중에서 가장 큰 값을 갖는 카드배열과 가장 작은 값을 갖는 카드배열을 찾아서 

그 값의 차이를 구하는 프로그램을 작성하시오.

 

 

입력형식

입력의 첫 번째 줄에는 전체 카드의 수를 나타내는 N과 선택하는 카드의 수 k와 제약조건의 수 P가 하나의 빈칸을 사이에 두고 주어진다. 

단, 3≤k≤300,000, 0≤P≤1,000,000이다.

두 번째 줄부터 P개의 줄에는 각 줄마다 하나의 제약조건을 나타내는 두 개의 정수 a,b가 하나의 빈칸을 사이에 두고 주어진다. 이는 제약조건 Ca＞Cb를 의미한다.

 

출력형식

제약조건을 만족하는 카드배열 중에서 가장 큰 값을 갖는 카드배열과 가장 작은 값을 갖는 카드배열을 찾고, 

그 값의 차이를 1,000,000,007로 나눈 나머지를 출력한다. 

  단, 제약조건을 만족하는 카드의 배열이 존재하지 않는 경우는 없다.

 

[테스트 데이터 조건]

• 전체 테스트 데이터의 20%는 N, k≤11.

• 전체 테스트 데이터의 40%는 N, k≤10,000.

 

입력 예

4 3 2

2 0

0 1

출력 예

21

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>

#define MAXN 300000
#define MAXM 1000000
#define TreeN 1048576
#define from Q[Head];


struct List {
    int a, b;    // a > b
};
int N, M, K;
List A[MAXM + 1];                //크기관계 저장
int S[MAXN + 1], F[MAXN + 1];    // 시적점에 대한 리스트 첫 좌표, 끝 좌표
int C[MAXN + 1], Cp[MAXN + 1];   // degree or node
int T[TreeN], Ti;                // 우선순위 큐 indexed tree 구현
int Result_s[MAXN + 1];          // 최소 결과값
int Result_b[MAXN + 1];          // 최대 결과값

bool SortF(List a, List b)
{
    return a.a < b.a;
}

void Input()
{
    int i;
    scanf("%d %d %d", &N, &K, &M);
    
    for (i = 1; i <= M; i++)
    {
        scanf("%d %d", &A[i].a, &A[i].b);
        // 번호 앞족부터 1로 시작하도록 변경
        A[i].b = K - A[i].b;
        A[i].a = K - A[i].a;
        
        C[A[i].b]++;
    }
    std::sort(A+1, A+M+1, SortF);

    for (i = 1; i <= M; i++)
    {
        if (A[i].a != A[i - 1].a)
            S[A[i].a] = i;

        F[A[i].a] = i;
    }
}

void Push(int x) {      // 우선순위 큐에 원소 추가
    T[Ti + x] = x;
    x += Ti;

    while (1)
    {
        x /= 2;
        if (x == 0)
            break;

        if (T[x * 2] < T[x * 2 + 1])
            T[x] = T[x * 2 + 1];
        else
            T[x] = T[x * 2];
    }
}

void Delete(int x) {    // 우선순위 큐에 원소 삭제
    T[Ti + x] = 0;
    x += Ti;

    while (1)
    {
        x /= 2;
        if (x == 0)
            break;

        if (T[x * 2] < T[x * 2 + 1])
            T[x] = T[x * 2 + 1];
        else
            T[x] = T[x * 2];
    }
}

void Precess(int c, int* Result)
{
    int i, n, tmp, dir;

    if (c == 0)
    {
        n = K - 1;
        dir = -1;
    }
    else
    {
        n = N - K;
        dir = 1;
    }

    Ti = 1;
    while (1)
    {
        if (Ti >= K)
            break;
        Ti *= 2;
    }

    Ti--;       // indexed tree 세팅

    for (i = 1; i <= K; i++)
    {
        if (C[i] == 0)       // 단말노드 push
            Push(i);
    }

    while (1)
    {
        if (T[1] == 0)
            break;
        tmp = T[1];
        Delete(T[1]);      // pop
        Result[tmp] = n;
        n += dir;

        if (S[tmp])       // 연결된 간선이 있을 때
        {
            for (i = S[tmp]; i <= F[tmp]; i++)
            {
                C[A[i].b]--;
                if (C[A[i].b] == 0)
                {
                    Push(A[i].b);
                }
            }
        }
    }
}

void Output()
{
    int i;
    __int64 bsum = 0, ssum = 0, tmp = 1;   // 리눅스 __int64_t

    for (i = K; i >= 1; i--)
    {
        ssum += Result_s[i] * tmp;
        bsum += Result_b[i] * tmp;
        tmp *= N;
        tmp %= 1000000007;
        ssum %= 1000000007;
        bsum %= 1000000007;
    }
    bsum -= ssum;

    if (bsum < 0)
        bsum += 1000000007;
    printf("%d", (int)bsum);
}

int main()
{
    int i, tmp;

    Input();

    std::sort(A + 1, A + M + 1, SortF);
    for (i = 1; i <= M; i++)
    {
        if (A[i].a != A[i - 1].a)
            S[A[i].a] = i;

        F[A[i].a] = i;
    }
    Precess(0, Result_s);    // 가장 작은 수 구하기

    for (i = 1; i <= K; i++)
        S[i] = F[i] = 0;

    for (i = 1; i <= M; i++)
    {
        tmp = A[i].a;
        A[i].a = A[i].b;
        A[i].b = tmp;

        C[A[i].b]++;
    }

    std::sort(A + 1, A + M + 1, SortF);
    for (i = 1; i <= M; i++)
    {
        if (A[i].a != A[i - 1].a)
            S[A[i].a] = i;

        F[A[i].a] = i;
    }
    Precess(1, Result_b);    // 가장 큰 수 구하기
    Output();
    return 0;
}