d573: CRC騎士團

2019-09-01

內容

在魔法之都-梅蘭城裡，有一群以維護世界秩序為己任的人。
他們是…CRC 騎士團！
隨著梅蘭城的魔法研究越來越順利、壞人越來越少，
加入 CRC 騎士團的人卻越來越多！

現在團長「加寬」要將所有的 CRC 騎士按照事先排定的名單進行編組，
但是名單的資料太過龐大，反而需要騎士的時候找不到他所屬的組別！
請你透過處理這筆名單，並接受一個騎士的編號，找出這個騎士所屬的組別。

輸入

共計 10 個測資點。
每個測資點有不超過 10 組的多組測試資料，
對於每組測試資料：
第一行有正整數 n(1<=n<=100000)，代表全部分組的組數
接下來的 n 行會有按照順序排列的 1n 組，
第一個數字是組的編號(1n)，第二個數字是本組的組員數 p(0<=p<=100000)，
接下來 p 個數字則是本組的所有騎士編號。
全部的騎士總數量 x(1<=x<=100000)，並且編號必定是 1~x。
(也就是說如果全部有 20 位騎士，那麼他們的編號就是 1,2,3,…,19,20，不會重複)
在測試資料的第 n+1 行(每組測資的最後一行)有一個數字 y 表示要查詢的騎士編號

3
1 5 1 2 3 4 5
2 2 6 7
3 9 8 9 10 11 12 13 14 15 16
1
5
1 0
2 1 3
3 2 4 5
4 3 6 7 9
5 4 8 1 2 10
5

輸出

請輸出欲查詢騎士編號的所屬組別編號。

1
3

解題思路

根據題意騎士人數總量不超過 100000 人，所以開一個陣列索引表示騎士團員編號，內容存放該團員為第幾組即可，

輸入測資很大，做輸入優化。

完整程式碼

AC (8ms, 1.5MB)

#include <stdio.h>

int member[100001], t;

#define BUFSIZ 1048576

inline char readChar()
{
    static char buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;
    if (now == end)
    {
        if (end < buffer + BUFSIZ)
            return EOF;
        end = (buffer + fread(buffer, 1, BUFSIZ, stdin));
        now = buffer;
    }
    return *now++;
}

inline char readUInt(unsigned int* dst)
{
    register char ch;
    while ((ch = readChar()) < '0')
        if (ch == EOF) return 0;
    *dst = ch ^ '0';
    while ((ch = readChar()) >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
    return 1;
}

int main()
{
    int n, g, m, t, tmp;
    while (readUInt(&n))
    {
        for (int i = 0; i < n; i++)
        {
            readUInt(&g), readUInt(&m);
            for (int j = 0; j < m; j++)
            {
                readUInt(&tmp);
                member[tmp] = g;
            }
        }
        readUInt(&t);
        printf("%d\n", member[t]);
    }
    return 0;
}