trang chủ / bài tập / pickhero

Chọn Tướng

Có hai đội, mỗi đội gồm $n$ người chơi, và tổng cộng $2 n$ vị tướng cần được chia cho hai đội. Hai đội lần lượt chọn tướng: đầu tiên đội $1$ chọn một tướng, sau đó đội $2$ chọn, rồi lại đến đội $1$ , và cứ thế xen kẽ. Mỗi tướng sau khi được chọn sẽ không còn để đội nào chọn nữa. Sau $2 n$ lượt, mỗi đội có đúng $n$ tướng.

Sức mạnh của tướng thứ $i$ là $p_{i}$ . Mỗi đội muốn tối đa hoá tổng sức mạnh các tướng của đội mình.

Ngoài ra có $m$ cặp khắc chế: khi một đội chọn một tướng thuộc một cặp khắc chế thì ngay ở lượt kế tiếp, đội kia buộc phải chọn tướng còn lại của cặp đó. Mỗi tướng thuộc nhiều nhất một cặp khắc chế.

Bạn điều khiển đội $t$ . Chương trình chấm sẽ điều khiển đội còn lại và có thể chơi không tối ưu; trong trường hợp đó bạn phải tận dụng để đạt tổng sức mạnh lớn nhất có thể. Nói chính xác: nếu tồn tại một chiến lược bảo đảm cho bạn đạt tổng sức mạnh ít nhất là $q$ bất kể đội kia chọn thế nào, thì bạn phải đạt được ít nhất $q$ .

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ .
Dòng thứ hai chứa $2 n$ số nguyên $p_{1}, p_{2}, \dots, p_{2 n}$ .
$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ ( $a \neq b$ ) mô tả một cặp khắc chế. Mỗi tướng xuất hiện nhiều nhất một lần trong danh sách này.
Dòng cuối chứa số nguyên $t$ (đội mà bạn điều khiển).

Các tướng được đánh số từ $1$ đến $2 n$ theo thứ tự trong dữ liệu vào.

Dữ liệu ra

Đây là bài toán tương tác. Bạn không đọc trọn dữ liệu một lần rồi in kết quả, mà trao đổi qua lại với hệ thống theo giao thức bên dưới.

Giao thức tương tác

Trò chơi diễn ra trong $2 n$ lượt. Ở mỗi lượt của bạn, in ra một số nguyên $x$ ( $1 \leq x \leq 2 n$ ) là chỉ số tướng bạn chọn. Tướng này phải chưa được chọn và phải tuân thủ luật cặp khắc chế (nếu bạn đang bị buộc phải chọn tướng còn lại của một cặp thì bắt buộc chọn đúng tướng đó).

Ở mỗi lượt của đội kia, đọc một số nguyên $x$ ( $1 \leq x \leq 2 n$ ) là chỉ số tướng mà đội kia chọn.

Nếu $t = 1$ bạn đi trước, ngược lại bạn đi sau. Sau lượt cuối cùng, kết thúc chương trình mà không in gì thêm.

Quan trọng: Sau mỗi lần in ra, bạn phải flush output:

C++: cout << endl; hoặc cout.flush();
Python: print(..., flush=True)

Nếu bạn thực hiện một lượt không hợp lệ, hệ thống sẽ kết thúc và bạn nhận kết quả sai.

Ràng buộc

$1 \leq n \leq 1000$
$0 \leq m \leq n$
$1 \leq p_{i} \leq 1000$
Bảo đảm mỗi tướng thuộc nhiều nhất một cặp khắc chế.

Ví dụ

Chương trình	Hệ thống	Giải thích
	3 1 1 2 3 4 5 6 2 6 1	Đọc dữ liệu: $n = 3$ , $m = 1$ , cặp khắc chế $(2, 6)$ , bạn là đội $1$ .
6		Bạn chọn tướng $6$ (mạnh nhất, sức mạnh $6$ ); vì $6$ thuộc cặp $(2, 6)$ nên đội kia bị buộc chọn $2$ .
	2	Đội kia buộc phải chọn tướng $2$ .
5		Bạn chọn tướng $5$ .
	4	Đội kia chọn tướng $4$ .
3		Bạn chọn tướng $3$ .
	1	Đội kia chọn tướng $1$ . Tổng của bạn là $6 + 5 + 3 = 14$ .

Chương trình	Hệ thống	Giải thích
	3 1 1 2 3 4 5 6 1 5 2	$n = 3$ , $m = 1$ , cặp khắc chế $(1, 5)$ , bạn là đội $2$ .
	6	Đội kia đi trước, chọn tướng $6$ .
5		Bạn chọn tướng $5$ ; vì $5$ thuộc cặp $(1, 5)$ nên đội kia bị buộc chọn $1$ .
	1	Đội kia buộc phải chọn tướng $1$ .
4		Bạn chọn tướng $4$ .
	3	Đội kia chọn tướng $3$ .
2		Bạn chọn tướng $2$ . Tổng của bạn là $5 + 4 + 2 = 11$ .

Bình luận

Không có bình luận tại thời điểm này.

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 5,00một phần

Giới hạn thời gian 1.0s

Giới hạn bộ nhớ 256M

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig