Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
VOXOR - XOR dãy số |
Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/voxor
Cho dãy A gồm N số nguyên không âm. Ta lần lượt thực hiện Q thao tác trên tập hợp này:
- XOR x: Với mọi i, Ai = Ai xor x
- FIND k: Tìm số lớn thứ k trong dãy A.
Yêu cầu: Thực hiện các truy vấn trên.
Input
Dòng đầu tiên ghi 2 số N và Q.
Dòng thứ hai ghi N số là giá trị ban đầu của dãy A.
Tiếp theo là Q dòng, mỗi dòng ghi 1 trong 2 loại truy vấn.
Output
Với mỗi truy vấn loại FIND, in ra kết quả tìm được.
Giới hạn
Subtask 1 (25%)
- N, Q ≤ 5000
- 0 ≤ Ai ≤ 109
- 0 ≤ x ≤ 109.
Các subtask 2, 3 và 4 tiếp theo đều có
- N ≤ 105
- Q ≤ 105
- 0 ≤ Ai ≤ 109
Subtask 2 (40%)
- 0 ≤ x ≤ 100
Subtask 3 (10%):
- 0 ≤ x ≤ 109
- x luôn có dạng 2k
Subtask 4 (25%):
- 0 ≤ x ≤ 109
Ví dụ
Input: 4 9 1 2 3 4 FIND 1 FIND 2 FIND 3 FIND 4 XOR 6 FIND 1 FIND 2 FIND 3 FIND 4
Output: 4 3 2 1 7 5 4 2
Giải thích
Trước truy vấn XOR 6, dãy số là 1 2 3 4.
Sau truy vấn XOR 6, dãy số là 7 4 5 2.
Được gửi lên bởi: | VOJ Team |
Ngày: | 2015-12-25 |
Thời gian chạy: | 1s |
Giới hạn mã nguồn: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Ngôn ngữ cho phép: | C C++ 4.3.2 PAS-GPC PAS-FPC TEXT |
Nguồn bài: | VNOI Online 2016 |
hide comments
2015-12-26 12:22:56 Luan
Sao mình nộp nó bảo "Wrong problem! " vậy ad :< |
|
2015-12-26 11:01:01 VOJ Team
"ad oi neu k> so cac so khac nhau thi sao a?" Lưu ý là đề yêu cầu in ra số lớn thứ k chứ không phải là giá trị lớn thứ k. |
|
2015-12-26 10:53:53 Dương Bảo
ad oi neu k> so cac so khac nhau thi sao a? |
|
2015-12-26 09:14:34 VOJ Team
"cho mình hỏi file inp và out tên gì thê" Standard input output nhé bạn. Tức là không để tên file. "ad oi neu k>n thi sao" Dữ liệu đảm bảo k <= N. |
|
2015-12-26 09:04:59
cho mình hỏi file inp và out tên gì thê |
|
2015-12-26 08:37:50 *
ad oi neu k>n thi sao |