TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

71.4% (5/7)

Submission's AC Ratio

33.3% (18/54)

Description

有一種(或許在墨西哥)很流行的個人遊戲叫做點連接遊戲

這個遊戲是一種獨人遊戲。就是一個盤上有g顆綠色棋子、r顆紅色棋子。

保證:

  1. 所有棋子座標都在0~s之間。
  2. (0,s),(s,s)這兩點有綠色棋子、(0,0),(s,0)這兩點有紅色棋子。 * 而且(0,s)一定是綠色1號、(s,s)是綠色2號、(0,0)是紅色1號、(s,0)是紅色2號。
  3. 任三顆棋子不共線。

你有兩種顏色的線可以用,綠線只能連接兩個綠點、紅線只能連接兩個紅點。

遊戲目標是希望你寫個程式用(g-1)條綠線讓所有綠點連通、用(r-1)條紅線讓所有紅點連通。

但任兩條線不能交叉。

例如,下圖就是一個完成的畫面:

本題為互動題,請引入#include "lib1631.h"並撰寫一個程式來完成他。

以下為可使用的函式:(注意:在這個互動題中 0代表綠色 1代表紅色)

void Init(int &gCnt, int &rCnt); 在作任何操作前請先呼叫此函式,gCnt為綠棋子個數、rCnt為紅棋子個數。

void Get(int color, int &x, int &y); color=0代表綠色、color=1代表紅色。

例如,第i次呼叫Get(0, x, y)會得到綠色棋子第i顆的x座標及y座標。超過該顏色棋子顆數的呼叫會得到一個WA

void Report(int color, int n1, int n2); 回報答案,表示你要把color顏色 編號n1和n2的兩個點連起來。

例如,Report(1, 1, 2)就是把紅色1跟紅色2連起來。

void Finish(void);表示結束回報線段,並開始檢測程式是否正確。之後會自動幫你結束程式。

一些保證:

3 <= g,r <= 50,000
0 < s <= 200,000,000

Input Format

本題無須讀入,任何讀入動作會得到一個WA。

Output Format

本題無須輸出,請Report()答案後Finish()。

Sample Input

3 (綠色點數)
0 5
5 5
2 1
3 (紅色點數)
0 0
5 0
3 4

Sample Output

Report(0, 1, 2);
Report(0, 2, 3);
Report(1, 1, 2);
Report(1, 1, 3);

Hints

1.一個保證不會AC的程式:
#include <cstdio>
#include "lib1631.h"

int pos[2][50001][2];
int cnt[2];
int main(){
 Init(cnt[0], cnt[1]);
 for(int i=0; i<=1; i++)
  for(int j=1; j<=cnt[i]; j++)
   Get(i, pos[i][j][0], pos[i][j][1]);

 for(int i=0; i<=1; i++)
  for(int j=1; j<cnt[i]; j++)
   Report(i, j, j+1);
 Finish();
}

還有,這題的judge程式速度非常慢,但是時間絕對夠正解在沒有特別設計過的測資上。

Problem Source

原TIOJ1631 / IOI '06 Joining Points
Problem Setter:ATP

Subtasks

No. Testdata Range Score
1 0 16
2 1 16
3 2 16
4 3 16
5 4 16
6 5 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 4000 65536 262144 1
1 4000 65536 262144 2
2 4000 65536 262144 3
3 4000 65536 262144 4
4 4000 65536 262144 5
5 4000 65536 262144 6