Test Message

Naukri Local Judge Mod

開始使用

這是什麼? 能做什麼?

這是一個 C/C++的本地 Judge 模組,它可以在輸入結束後自動幫你比對測資,免除線上判斷時的麻煩和等待時間。

他能夠幫助你:

  1. 取消 4996 警告(scanf()等函式的不安全警告)
  2. 取消 scanf() 不接受回傳值時的警告
  3. 本地 Judge (支援 Tolerant 、 Strictly 、 Special 三種模式)
  4. 簡單的效能評估

安裝

以下為在 Visual Studio 安裝的流程

  1. 下載本模組

  2. 新增一個空白專案,並在專案中加入一個名為 main 的.c 或.cpp 檔

  3. 新增 include 目錄到專案

    專案 → 屬性 → C/C++ → 一般 → 其他 Include 目錄 → 指定模組資料夾

  4. 把模組中的 systemInput.txt、systemOutput.txt、userOutput.txt 移動至專案資料夾 (你寫程式的.c/.cpp 檔那裡)。

    以 Project 專案為例,在 Project/Project/ 這層會看到 main.c,把 3 個 txt 檔丟到這裡。

  5. 如果使用的是 cpp,將模組中全部的.c 檔改為.cpp。

侵入式安裝

這步驟不會為你添加任何實質性的功能,但可以在寫程式時不用再引入本模組的標頭檔,從而獲得更好的使用體驗,但如果除了 Online Judge 之外還要寫其他 C/C++的程式則不建議使用。

  1. 先備份好 stdio.h 避免出錯。

  2. 做完以上述動作後,開啟 main.c 輸出

    #include <stdio.h>

  3. 在上面右鍵 → 前往<stdio.h>

  4. 滑到最下面,在#endif 上加上

    #include <naukri.h>

    變成

    … (其他在上面的程式碼)
    #include <naukri.h>
    #endif

  5. 儲存,如果你的 Visual Studio 沒有該資料夾的存取權限他會提示你另存新檔,把它存到桌面在手動貼到該資料夾覆蓋即可。
    資料夾可以在 stdio.h 頁籤上右鍵 → 開啟收納資料夾找到。

操作

使用方式

選好 Judge 模式(參見判斷模式),在#include <stdio.h> 下引入 naukri.h 變成

#include <stdio.h>
#include <naukri.h>

即可使用,上傳至 OJ 時記得刪掉 #include <naukri.h> 就可以了。
若為侵入式安裝則不必引入(除非你不會用到 stdio.h),像沒安裝模組時一樣寫程式即可。

若你使用的是 cpp,iostream 和 cstdio 內部都會引入 stdio.h。

情境範例

請先閱讀下方的巨集與定義

已經有輸入和正確的輸出
  1. 在 FILE_INPUT 放輸入,在 FILE_COMPARE 放正確的輸出
  2. 定義 IO 模式為 F_TF (FILE_INPUT 輸入、終端 + FILE_OUTPUT 輸出)
  3. 將 CMPMODE 設為 2 (或將函式 main() return 2)
  4. 開始運行。
已經有輸入和正確的程式碼
  1. 在 FILE_INPUT 放輸入
  2. 定義 IO 模式為 F_TF (FILE_INPUT 輸入、終端 + FILE_OUTPUT 輸出)
  3. 將 CMPMODE 設為 3 (或將函式 main() return 3)
  4. 開始運行。
只有正確的程式碼,想用終端機測試
  1. 定義 IO 模式為 T_TF (終端輸入、終端 + FILE_OUTPUT 輸出)
  2. 將 CMPMODE 設為 3 (或將函式 main() return 3)
  3. 開始運行,輸入自定義測資。 (也可以將自定義測資放到 FILE_INPUT 用 “已經有輸入和正確的程式碼” 判斷)
什麼都沒有,只是想使用包裝過的函式
  1. 定義 IO 模式為 T_T (終端輸入、終端輸出)
  2. 將 CMPMODE 設為 1 (或將函式 main() return 1)
  3. 開始運行。

巨集與定義

判斷模式

比較時的預設參數。

CMPMODE

定義預設的 Judge 的方式,而 main.c 的 return 值可以用來覆蓋這個預設模式(也就是如果 return 不為 0 則以 return 值為準)

0 = 隨意(若 return 亦為 0 則不進行比較)
1 = 不進行比較
2 = 使用 FILE_COMPARE 儲存的答案比較
3 = 使用 judge.c 計算出的答案比較 (這個模式只有在使用 FILE_INPUT 作為輸入時才能使用)
4 = 自動判斷,如果輸入來自終端機 = 2, 來自檔案 = 3

STRICTLYMODE

嚴格比對模式,當 STRICTLYMODE 為 0 時代表關閉,亦即是寬容(Tolerant)模式,為 1 時開啟則是嚴格(Strictly)模式,預設值為 0

TLE

定義超時時間限制,以毫秒為單位,預設值為 1000 ms
注意!它不會在你超時時跳出程式,只會在印出判斷結果時提醒你超時了。

文件位置

輸入輸出檔存放位置,可在 naukri.h 進行自定義修改

FILE_INPUT

輸入檔位置,預設值為 input.txt

FILE_OUTPUT

使用者輸出檔位置,預設值為 output.txt

FILE_COMPARE

比對用檔案位置,也是判斷程式輸出檔,預設值為 compare.txt

IO 流

這部分僅供模組使用,若無客製化需求只要注意不要誤用關鍵字即可。

stdin

當輸入選擇 FILE_INPUT 時會覆寫 stdio.h 對 stdin 的定義。

本巨集僅用於將 freed() 等未被包裝的輸入函式指向正確的輸入位置,在被包裝的函式中,內部會強制將流導向定義的 fileIn 或 termIn 。

termIn

終端輸入流

termOut

終端輸出流

termErr

終端錯誤流

fileIn

檔案輸入流

fileOut

檔案輸出流

fileCmp

檔案比對流

IO 修正

LFFIX

定義是否將 gets(),fgets() 讀入字串末端的換行符號 ('\n') 移除

0 = 不移除字串尾的換行符號
1 = 移除字串尾的換行符號

IO 模式

使用 wrapper 包裝平常會使用到的輸入輸出方式。
IO 模式是預設為 F_TF,你可以在 naukri.h 進行更改,若只是要暫時的更改做測試則在 main.c 的 #include <naukri.h> 之前定義你要的模式 Ex:

#define F_TF
#include <stdio.h>
#include <naukri.h>

就會變成 F_TF 模式。

NO_WRAPPER

不包裝,也就是使用原生的 IO 模式

T_T

使用終端機作為輸入,並將結果輸出至終端機,和不包裝一樣,差別在它能讓不接受回傳值時的警告消失。

T_F

使用終端機作為輸入,並將結果輸出至 FILE_OUTPUT。

T_TF

使用終端機作為輸入,並將結果輸出至終端機和 FILE_OUTPUT。

F_T

使用 FILE_INPUT 作為輸入,並將結果輸出至終端機。

F_F

使用 FILE_INPUT 作為輸入,並將結果輸出至 FILE_OUTPUT。

F_TF

使用 FILE_INPUT 作為輸入,並將結果輸出至終端機和 FILE_OUTPUT。

F_C

使用 FILE_INPUT 作為輸入,並將結果輸出至 FILE_COMPARE,這是給 judge.c 使用的巨集。

F_TC

使用 FILE_INPUT 作為輸入,並將結果輸出至終端機和 FILE_COMPARE,這是給 judge.c 使用的巨集。

被包裝的函式

除了輸入輸出(參照IO 模式)位置外,他們不會對你的程式造成任何影響,你可以像沒有包裝時一樣使用他們。但要注意為了讓模組能夠正常的運行,這些被包裝的函式可能會產生額外的運算。

  • scanf(_Format, …)
  • gets(_Buffer)
  • fgets(_Buffer, _MaxCount, _Stream)
  • getchar()
  • printf(_Format, …)
  • puts(_Buffer)
  • putchar(_Character)

注意事項

  • judge.c 最上方會有預設的引入,這是使用程式碼進行判斷時的必要引入,請不要將它刪掉,如果不慎誤刪在 naukri.h 最底部有一個被註解掉的備份可以還原。

  • 時間判斷是使用 CPU 的 clock 數來計算,因此在終端機等候輸入和使用中斷點 Debug 的時都會被計入,若想要獲得較正確的時間評估請使用 FILE_INPUT 做輸入並關閉所有中斷點。

  • 模組中使用的全域函式或變數皆以雙底線開頭、單底線結尾(__func_()),是為了避免和使用者定義的函式衝到,請不要使用這種命名方式。

  • main.c 的 main() 會被用巨集定義成 __main_()、 judge.c 的 main() 則會被定義成 __judge_(),這些是為了先載入模組的必要定義,模組載入後會自己呼叫 __main_() 和 __judge_() ,不必擔心。

  • 如果 main.c 和 judge.c 的變數或函式撞名,系統會報錯並顯示該變數(函式)已經在 judge.obj 定義過了,這時候只要把 judge.c 裡面的撞名變數(函式)前面加上 static 前綴即可。

d636: 大爆炸bomb

內容

2^31 是 2 的 31 次方的意思(2147483648)
10^100 這個數字意味著 1 後面有 100 個 0
魔法師小米企鵝因為練功的時候一邊唸咒語一邊打瞌睡
居然莫名其妙召喚了好多個這種可怕的數學題目…
幫幫睡著的小米企鵝好嗎?


輸入

每個測資點僅一組測資,不必 EOF 讀檔。
測資包含一列兩個數字 a 和 b (1<=a<=65535 , 1<=b<=2147483647)

2 31

輸出

請輸出 a^b 的值,為了避免數字太大,將結果 mod10007 輸出就可以了!

1462


解題思路

用費馬小定理求解。


完整程式碼

AC (2ms, 104KB)
#include <stdio.h>
#define MOD 10007

int flt(int a, int b)
{
int res = 1, next = a % MOD;
for (int i = 0; i < 32; i++)
{
if (b & 1)
res = res * next % MOD;
next = next * next % MOD;
b >>= 1;
}
return res;
}

int main()
{
int a, b;
scanf(" %d %d", &a, &b);
printf("%d\n", flt(a, b));
return 0;
}

d626: 小畫家真好用

內容

Windows 的小畫家真好用!
(至少在處理 PrintScreen 方面蠻快的…)
大家都知道
小畫家裡面有一種繪圖工具
叫做油漆桶工具
只要選定你要的顏色、油漆的地點就可以進行填色
油漆桶的填色範圍是取決於”同色塊相鄰”的原則
現在請你模擬這項工具


輸入

每個測資點只有一筆測資。
第一行有整數 n(1<=n<=100)表示這張圖的大小是(nn)個字元
接下來的 n 行,每行 n 個字元表示這張圖的樣子。
只有+、-兩種字元組成(兩種顏色的意思)
在最後一行,有兩個整數 i,j 表示油漆桶點擊的地點是第(i+1)列第(j+1)個字元,
[
假設有圖如下 3*3:
012
0---
1-+-
2-++
那麼 0,2 就表示這格:
012
0--\

1-+-
2-++
]
請視選取的顏色為+,選取的位置原本的顏色必為-
並且墨水只會利用上下左右四個方位擴散

7
-------
-+++---
-+--+--
-+---+-
--+++--
---++--
-------
3 4

輸出

請直接輸出經過油漆桶塗色後的圖案

-------
-+++---
-++++--
-+++++-
--+++--
---++--
-------


解題思路

用 dfs 從目標點開始遍歷所有可能,遇到'-'就將他改為'+‘\,遇到'+'則返回,遍歷完畢後輸出更新後的圖即可。

注意處理邊界問題。


完整程式碼

AC (2ms, 112KB)
#include <stdio.h>

char map[110][110];

void dfs(int r, int c)
{
if (map[r][c] == '+' || !map[r][c])
return;
map[r][c] = '+';
dfs(r, c + 1);
dfs(r + 1, c);
dfs(r, c - 1);
dfs(r - 1, c);
}

int main()
{
int n, r, c;
scanf(" %d", &n);
for (int i = 1; i <= n; i++)
scanf(" %s", map[i] + 1);
scanf(" %d %d", &r, &c);
dfs(r + 1, c + 1);
for (int i = 1; i <= n; i++)
puts(map[i] + 1);
return 0;
}

d623: 反方陣

內容

11


輸入

輸入有兩行每行有 2 個數字代表 2 階方陣

輸入 4 個 0 表示結束

1 2
3 4
1 1
1 1
0 0
0 0

輸出

輸出此方陣的反方陣

若此方陣無反方陣則輸出 cheat!

-2.00000 1.00000
1.50000 -0.50000
cheat!


解題思路

實作數學的反方陣。


完整程式碼

AC (3ms, 64KB)
#include <stdio.h>

int main()
{
double a, b, c, d, det;
while (scanf("%lf %lf %lf %lf", &a, &b, &c, &d) == 4 && a + b + c + d)
{
det = a * d - b * c;
if (det)
printf("%.5lf %.5lf\n%.5lf %.5lf\n", d / det, -b / det, -c / det, a / det);
else
puts("cheat!");
}
return 0;
}

d587: 參貳壹真好吃

內容

參貳壹真是太好吃了!
現在有一連串由 1、2、3 這三個數字組成的數列,
請你把他們由小到大排好好嗎?


輸入

本題有 2 個測資點,每個 50 分,每個測資點只有一組測資。
第一行有整數 n(1<=n<=1000000)代表接下來的數列有幾個數字
第二行就是這 n 個包含 1、2、3 的數字

9
1 1 1 2 2 3 3 3 2

輸出

對於每組測資,請輸出一行由小到大 1~3 排好的結果。

1 1 1 2 2 2 3 3 3


解題思路

簡單的基數排序,由於輸出只有 1, 2, 3 三種可能所以建好表直接用 fputs()輸出字串節省 printf()的運算時間。


完整程式碼

AC (3ms, 116KB)
#include <stdio.h>

int list[4];
char outstr[4][3] = { "", "1 ", "2 " , "3 " };

int main()
{
int n, tmp;
scanf(" %d", &n);
for (int i = 0; i < n; i++)
{
scanf(" %d", &tmp);
list[tmp]++;
}
for (int i = 1; i <= 3; i++)
{
while (list[i]--)
fputs(outstr[i], stdout);
}
return 0;
}

d584: 技能點數skill

內容

在楓之谷這個線上遊戲裡,
每個人創角色剛開始都是 1 級的初心者,初心者只有”初心者技能點數”,不特別計算。
8 級可以轉職成為法師,10 級可以轉職成為劍士、弓箭手、盜賊。
轉職後可以拿到技能點數 1 點,並且在往後每次升級都可以得到 3 點技能點數。
30 級解任務打完討厭的黑色珠子以後,
可以進行第二次轉職,拿到 1 點技能點數。
70 級進行第三次轉職,天阿…要和一轉教官的分身 PK,
打贏就可以第三次轉職,拿到 1 點技能點數。
好不容易練到 120 級四轉,解了超討厭的轉職任務以後,
第四次轉職可以拿到三點技能點。
最高 200 級封頂。

現在梅蘭和吳企鵝都玩膩冰雷大魔導士和主教了,
他們正在計畫練分身,請你幫他們算一算某個等級的某職業有多少技能點數呢?


輸入

本題有三個測資點,每個測資點有多組測試資料。
每組測試資料一行,有兩個正整數。
第一個正整數表示這個角色的職業,0 是初心者、1 是劍士、2 是法師、3 是弓箭手、4 是盜賊
第二個正整數表示這個角色的等級 lv(1<=lv<=200)

0 1
0 9
0 200
1 10
3 11
4 29
4 30
2 30
1 50
3 70
2 120
4 200

輸出

按照說明寫的規則,請輸出這個角色的一生會拿到多少技能點數。
請注意: 1.初心者沒有技能點數,甚至有一種超級初心者完全不轉職可以練到 100 多等甚至 200! 2.我們假設要玩法師的人會乖乖在 8 等一轉,其它在 10 等一轉,
並且他們到了 30、70、120 級也會乖乖自動去轉職。
(也就是假設等級輸入 70,那麼請把一轉、二轉、三轉附贈的技能點數都算進去)

0
0
0
1
4
58
62
68
122
183
342
576


解題思路

簡單的條件判斷。


完整程式碼

AC (2ms, 104KB)
#include<stdio.h>

int main()
{
int occ, lv, ans;
while (scanf(" %d %d", &occ, &lv) == 2)
{
if (occ == 0)
ans = 0;
else if (occ == 2)
{
ans = (lv - 8) * 3;
if (lv >= 120)
ans = ans + 6;
else if (lv >= 70)
ans = ans + 3;
else if (lv >= 30)
ans = ans + 2;
else if (lv >= 8)
ans = ans + 1;
}
else
{
ans = (lv - 10) * 3;
if (lv >= 120)
ans = ans + 6;
else if (lv >= 70)
ans = ans + 3;
else if (lv >= 30)
ans = ans + 2;
else if (lv >= 10)
ans = ans + 1;
}
printf("%d\n", ans);
}
return 0;
}

d583: 幼稚的企鵝

內容

小企鵝總是天真可愛,但擺脫不了幾分幼稚。
現在企鵝幼稚園的企鵝老師要小企鵝任意排隊。
而小企鵝們卻很堅持要照老師給他們的座號來排隊,
偏偏有的小企鵝就是會忘記自己的座號亂排,
於是可以想見的是一群短鳥喙的小企鵝爭吵互啄的景象了…


輸入

本題有 2 個測資點,每個 50 分,每個測資點有多組測資。
每組測資的第一行有整數 n(1<=n<=100000)代表有幾隻企鵝。
第二行則有 n 個數字的數列代表每隻企鵝的座號,並且座號必定有 1~n 不重覆。

10
9 5 10 4 3 6 1 2 7 8
30
30 29 28 27 26 25 10 11 12 13 15 14 16 19 18 17 20 24 23 22 21 8 9 7 6 5 3 4 2 1

輸出

請由小到大輸出已經排序的數列。

1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30


解題思路

簡單得排序,排序量很大,使用 quicksort 排序。


完整程式碼

AC (33ms, 616KB)
#include <stdio.h>
#include <stdlib.h>

int n, m, i, j;
int list[100010];

int cmp(const int* lhs, const int* rhs)
{
return (*lhs) - (*rhs);
}

int main()
{
while (scanf(" %d", &n) == 1)
{
for (int i = 0; i < n; i++)
scanf("%d", &list[i]);
qsort(list, n, sizeof(int), cmp);
for (int i = 0; i < n; i++)
printf("%d ", list[i]);
putchar('\n');
}
return 0;
}

d575: 末日審判

內容

傳說在「巴拉巴拉巴拉」(王國名稱)王國曾經有一個被屠殺的小鎮叫做「巴拉巴拉巴拉」(小鎮名稱)
後來「巴拉巴拉巴拉」王國有一群「巴拉巴拉巴拉」(也許是科學家或魔法師之類的)
他們研究發現,「巴拉巴拉巴拉」小鎮被屠村原來是因為遭到了天譴。
特別的是,末日審判的範圍是十字型擴張的。

在方格座標上(假設最中央的格子是 0,0,右 0,1,上-1,0,左 0,-1,下 1,0),
假如範圍是 1,中心座標是 0,0,那麼末日審判的範圍即是下圖的 ● 部分…

○○○○○
○○●○○
○●●●○
○○●○○
○○○○○

範圍 2

○○●○○
○●●●○
●●●●●
○●●●○
○○●○○

範圍 3

○○○●○○○
○○●●●○○
○●●●●●○
●●●●●●●
○●●●●●○
○○●●●○○
○○○●○○○

現在給定審判的中心座標、以及「巴拉巴拉巴拉」王國首都「巴拉巴拉巴拉」(城市名稱)的位置、審判範圍,
請你判斷首都會不會遭受天遣而滅亡。


輸入

共計 10 個測資點。

每個測資點有多組測試資料。
每組測資一行。
第一和第二個數字是天遣的中心座標,
第三和第四個數字是王國首都的座標,(所有座標值保證介於-2147483648~2147483647 之間)
第五個數字是天遣的有效範圍 r(1<=r<=2147483647)

0 0 1 1 1
0 0 1 1 2
0 0 -1 2 3
-1 0 1 2 3
0 0 50 50 100
0 0 50 50 99

輸出

如果首都座標在天遣的範圍內而招致滅亡,請輸出 die
如果首都座標不在天遣範圍而逃過一劫,請輸出 alive

alive
die
die
alive
die
alive


解題思路

審判的距離為曼哈頓距離,所以先求出審判起點和王都的曼哈頓距離後和審判距離比較即可。

輸入測資很大,記得做輸入優化。


完整程式碼

正常版

AC (0.4s, 104KB)
#include <stdio.h>

long long gap(long long num1, long long num2)
{
return num1 > num2 ? num1 - num2 : num2 - num1;
}

int main()
{
long long dx, dy, cx, cy, da;
while (scanf(" %lld %lld %lld %lld %lld", &dx, &dy, &cx, &cy, &da) == 5)
{
puts(gap(dx, cx) + gap(dy, cy) > da ? "alive" : "die");
}
return 0;
}

輸入優化版

AC (78ms, 1.1MB)
#include <stdio.h>
#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 readLongLong(long long* dst)
{
register char ch;
while ((ch = readChar()) < '-')
if (ch == EOF) return 0;
if (ch == '-')
{
*dst = readChar() ^ '0';
while ((ch = readChar()) >= '0')
* dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
*dst = ~*dst + 1;
}
else
{
*dst = ch ^ '0';
while ((ch = readChar()) >= '0')
* dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
}
return 1;
}

long long gap(long long num1, long long num2)
{
return num1 > num2 ? num1 - num2 : num2 - num1;
}

int main()
{
long long dx, dy, cx, cy, da;
while (readLongLong(&dx) & readLongLong(&dy) & readLongLong(&cx) & readLongLong(&cy) & readLongLong(&da))
{
puts(gap(dx, cx) + gap(dy, cy) > da ? "alive" : "die");
}
return 0;
}

d574: 節約符咒

內容

梅蘭城的法師們研究出了一種魔法道具:符咒。
即便是未曾學習魔法的人,
只要念出符咒上獨特的咒語就能施展特定魔法,
並且該咒語的魔力就會消失。

現在為了訓練新進的法師,需要使用大量的符咒。
但是梅蘭城(不事生產的)法師們並不會造紙這種技術,必須從首都艾克隆購買。

在紙張有限的情況下,
必須按照特定的規則來記述這些為數龐大的咒語才行。
假設有一張地震術符咒的內容是:aaabb
咒語是由三個 a 和兩個 b 所組成,所以在符咒上的記述內容必須改成:3a2b
並且咒語的每個字都是有順序的,假如符咒治癒術是 xxxyywwyy 的話,必須記作 3x2y2w2y,”y”的部分不能記作 4y
如果採取這個格式後沒有得到咒文的節約,那麼就選擇直接使用原本的咒語就可以了。

然而…

越強的法術寫出來的咒文就會越臭長!快寫個程式幫助魔法師節約咒文吧!
(他們總是基於好奇喜歡對電腦這東西施展破壞性的閃電魔法,所以沒人知道怎麼寫程式。)


輸入

共計 10 個測資點。

每個測資點只有一組測試資料。
第一行有正整數 n(1<=n<=10000000),表示原本咒文的長度(以字元為單位)
第二行則是咒文的內容連續的 n 個字元。
其中咒文的字元是由小寫字母所組成。

20
aaaaabbbbbcccccaabba

3
abc

輸出

如果簡化過的咒文長度小於原咒文,則輸出簡化版本
如果簡化後和原咒文字數相同甚至更多,則輸出原咒文

5a5b5c2a2b1a

abc


解題思路

簡單的字串處理。


完整程式碼

AC (28ms, 6.6MB)
#include <stdio.h>
#define MAX 10000000

char input[MAX], output[MAX];

char* setUInt(char buffer[], register unsigned int src, const char suffix)
{
register unsigned int div;
char tmp[11], * st = tmp + 10, *res = buffer - 1;
*st = 0;
do
{
*(--st) = src - ((div = src / 10) << 3) - (div << 1) + '0';
} while (src = div);
while (*++res = *st++)
;
if (suffix)* res++ = suffix;
return res;
}

int main()
{
int n, count;
char curr, * oTop;
while (scanf(" %d %s", &n, input) == 2)
{
curr = input[0], count = 1, oTop = output;
for (int i = 1; i < n; i++)
{
if (curr == input[i])
count++;
else
{
oTop = setUInt(oTop, count, curr);
curr = input[i], count = 1;
}
}
oTop = setUInt(oTop, count, curr);
puts(oTop - output < n ? output : input);
}
return 0;
}

d573: CRC騎士團

內容

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

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


輸入

共計 10 個測資點。
每個測資點有不超過 10 組的多組測試資料,
對於每組測試資料:
第一行有正整數 n(1<=n<=100000),代表全部分組的組數
接下來的 n 行會有按照順序排列的 1n 組,
第一個數字是組的編號(1
n),第二個數字是本組的組員數 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;
}
15678927