TopCoder

User's AC Ratio

100.0% (15/15)

Submission's AC Ratio

19.3% (32/166)

Description

X教授展示了他的最新發明: 珠鍊交換器(the Ultimate Bead Swapper,UBS)。
顧名思義,就是一個能通過交換一些珠子使珠鍊更有趣的工具。

UBS有 N 條平行於南北方向的傳送帶,已按照從左到右的順序 1 至 N 編號。

每條傳送帶的速度相同,且都是由北向南傳送。

有 M 個交換器,每個交換器都安放在某兩個相鄰的傳送帶上,
任意兩個交換器與傳送帶最北端的距離都是不同的(也就是說,所有的交換器可以按照它們與傳送帶最北端的距離嚴格排序)。

所有的交換器按從北到南的順序 1 到 M 編號。

圖 1 為一個 UBS 的俯視圖:

圖 1 一個擁有5條傳送帶和5個交換器的UBS

在使用UBS的時候,將N個珠子分別放在每條傳送帶的最北端,
這樣在傳送帶向南傳送時,所有的珠子一直保持在同一條水平橫線上。

當兩顆珠子同時到達一個交換器時,在右邊傳送帶上的珠子被移動到左邊的傳送帶上,
同時左邊傳送帶上的珠子被移動到右邊的傳送帶上。
經交換後,這兩個珠子仍保持與其他珠子在一條水平線上。

圖 2 所示為一次交換的過程:

圖2 (a)4顆珠子被傳送帶傳送 (b)在經過交換器後,2號和3號珠子交換了順序

編寫一個程序,對於給定的傳送帶條數N,交換器個數M,以及每個交換器的位置,回答以下形式的問題:
給出A(傳送帶的編號)和B(交換器的編號),
當所有的珠子都剛好完全經過交換器B(又稱B號交換器)時,最開始時放在第A條傳送帶(又稱A號傳送帶)最北端的珠子現在位於哪一條傳送帶上。

Input Format

第一行包含傳送帶的條數 N (2 ≤ N ≤ 300000)和交換器的個數 M (1 ≤ M ≤ 300000)。

接下來的M行,按照從北向南的順序描述所有的交換器,
每行包含一個整數P(1 ≤ P ≤ N-1),
表示在傳送帶P和P+1之間有一個交換器。

題為互動題,需要引入標頭檔#include "lib1739.h"

當讀取以上所描述的輸入資料後,你的程式必須呼叫以下所列的函式。

int getNumQuestions();
回傳你的程式必須回答的問題數目。

void getQuestion(int &A, int &B);
A 會被設定成一個輸送帶編號,來指定起初被放在UBS該輸送帶北端之串珠。
B 會被設定成所指定交換器的編號。

void answer(int ans);
對最近一次呼叫getQuestion讀取到的問題,回答其解答為ans。

這裡我們要特別強調,函式 getNumQuestions 必須先被呼叫,且只能被呼叫一次。
函式getQuestion及answer必須被交替呼叫:
在呼叫函式getQuestion後,你的程式必須先呼叫函式answer後,才能再呼叫getQuestion,反之亦同。

下面列出了呼叫的順序:

  1. 呼叫函式getNumQuestions取得Q值(1 ≤ Q ≤ 300,000),Q值表示接下來要給定的問題數目。
  2. 接下來必須執行 Q 次以下指令: (a)呼叫函式getQuestion 取得一組問題。 (b)呼叫函式answer 來回答所取到該組問題的解答。

若你的程式違反這個規定,你將得到WA。另外,由於函式庫亦有使用<cstdio>標頭檔進行內部的資料處理,請使用scanfprintf進行輸入/輸出。

注意:getQuestion()是傳reference。

提供範例程式和範例標頭檔下載

在使用範例程式的時候,你需要將詢問寫在輸入後面,格式如下。

接在輸入後的第一行包含一個整數,表示問題的個數Q,
接下來的Q行,每一行包含兩個整數值A及B,其中A表示輸送帶的編號,而B表示交換器的編號。

Output Format

僅表示在Sample Ouput的兩次詢問的答案。

在實際程式中,要輸出答案請使用answer函式。

Sample Input

5 5
2
4
1
3
3

2
3 4
5 5

Sample Output

1
4

Hints

Problem Source

原TIOJ1739 / APIO '08

Subtasks

No. Testdata Range Score
1 0 5
2 1 5
3 2 5
4 3 5
5 4 5
6 5 5
7 6 5
8 7 5
9 8 5
10 9 5
11 10 5
12 11 5
13 12 5
14 13 5
15 14 5
16 15 5
17 16 5
18 17 5
19 18 5
20 19 5

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1500 262144 262144 1
1 1500 262144 262144 2
2 1500 262144 262144 3
3 1500 262144 262144 4
4 1500 262144 262144 5
5 1500 262144 262144 6
6 1500 262144 262144 7
7 1500 262144 262144 8
8 1500 262144 262144 9
9 1500 262144 262144 10
10 1500 262144 262144 11
11 1500 262144 262144 12
12 1500 262144 262144 13
13 1500 262144 262144 14
14 1500 262144 262144 15
15 1500 262144 262144 16
16 1500 262144 262144 17
17 1500 262144 262144 18
18 1500 262144 262144 19
19 1500 262144 262144 20