IOI 2021 - Ngày 1

Cô Khong đang chuẩn bị \(n\) hộp kẹo cho học sinh của một ngôi trường gần nhà. Các hộp được đánh số từ \(0\) đến \(n-1\) và ban đầu đều rỗng. Hộp \(i\) (\(0 \le i \le n-1\)) có sức chứa \(c[i]\) viên kẹo.

Cô Khong dành \(q\) ngày để chuẩn bị các hộp kẹo. Vào ngày \(j\) (\(0 \le j \le q-1\)), cô thực hiện một thao tác được xác định bởi ba số nguyên \(l[j]\), \(r[j]\) và \(v[j]\), trong đó \(0 \le l[j] \le r[j] \le n-1\) và \(v[j] \ne 0\). Với mỗi hộp \(k\) thỏa mãn \(l[j] \le k \le r[j]\):

• Nếu \(v[j] > 0\), cô Khong thêm lần lượt từng viên kẹo vào hộp \(k\), cho đến khi đã thêm đúng \(v[j]\) viên kẹo hoặc hộp đầy. Nói cách khác, nếu trước thao tác hộp có \(p\) viên kẹo, thì sau thao tác hộp có số viên kẹo là:

• Nếu \(v[j] < 0\), cô Khong lấy lần lượt từng viên kẹo ra khỏi hộp \(k\), cho đến khi đã lấy ra đúng \(-v[j]\) viên kẹo hoặc hộp rỗng. Nói cách khác, nếu trước thao tác hộp có \(p\) viên kẹo, thì sau thao tác hộp có số viên kẹo là:

Nhiệm vụ của bạn là xác định số kẹo trong mỗi hộp sau \(q\) ngày.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v);

• c: mảng độ dài \(n\). Với \(0 \le i \le n-1\), \(c[i]\) là sức chứa của hộp \(i\).
• l, r, v: ba mảng độ dài \(q\). Vào ngày \(j\), với \(0 \le j \le q-1\), cô Khong thực hiện thao tác được xác định bởi \(l[j]\), \(r[j]\) và \(v[j]\) như mô tả ở trên.
• Hàm phải trả về một mảng \(s\) độ dài \(n\). Với \(0 \le i \le n-1\), \(s[i]\) phải là số kẹo trong hộp \(i\) sau \(q\) ngày.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): \(n\).
• Dòng \(2\): \(c[0]\ c[1]\ \ldots\ c[n-1]\).
• Dòng \(3\): \(q\).
• Dòng \(4+j\) (\(0 \le j \le q-1\)): \(l[j]\ r[j]\ v[j]\).

Dữ liệu ra

Trình chấm mẫu in câu trả lời theo định dạng sau:

• Dòng \(1\): \(s[0]\ s[1]\ \ldots\ s[n-1]\).

Ràng buộc

• \(1 \le n \le 200\,000\).
• \(1 \le q \le 200\,000\).
• \(1 \le c[i] \le 10^9\) với mọi \(0 \le i \le n-1\).
• \(0 \le l[j] \le r[j] \le n-1\) với mọi \(0 \le j \le q-1\).
• \(-10^9 \le v[j] \le 10^9\), \(v[j] \ne 0\) với mọi \(0 \le j \le q-1\).

Phân nhóm

Ví dụ

distribute_candies([10, 15, 13], [0, 0], [2, 1], [20, -11])

[0, 4, 13]

Nguồn

IOI 2021, Ngày 1 — Distributing Candies (candies).

Kiến trúc sư Timothy đã thiết kế một trò chơi thoát hiểm mới. Trong trò chơi có \(n\) phòng, được đánh số từ \(0\) đến \(n-1\). Ban đầu, mỗi phòng có đúng một chìa khóa. Mỗi chìa khóa thuộc một loại, là một số nguyên từ \(0\) đến \(n-1\), bao gồm cả hai đầu mút. Chìa khóa trong phòng \(i\) (\(0 \le i \le n-1\)) thuộc loại \(r[i]\). Lưu ý rằng nhiều phòng có thể chứa chìa khóa cùng loại, tức là các giá trị \(r[i]\) không nhất thiết khác nhau.

Trò chơi còn có \(m\) đường kết nối hai chiều, được đánh số từ \(0\) đến \(m-1\). Đường kết nối \(j\) (\(0 \le j \le m-1\)) nối hai phòng khác nhau \(u[j]\) và \(v[j]\). Một cặp phòng có thể được nối bằng nhiều đường kết nối.

Trò chơi dành cho một người chơi, thu thập chìa khóa và di chuyển giữa các phòng qua các đường kết nối. Người chơi đi qua đường kết nối \(j\) khi sử dụng nó để di chuyển từ phòng \(u[j]\) đến phòng \(v[j]\) hoặc ngược lại. Người chơi chỉ có thể đi qua đường kết nối \(j\) nếu trước đó đã thu thập được một chìa khóa loại \(c[j]\).

Tại bất kỳ thời điểm nào trong trò chơi, người chơi đang ở một phòng \(x\) và có thể thực hiện hai loại hành động:

• Thu thập chìa khóa loại \(r[x]\) trong phòng \(x\) (nếu chưa thu thập chìa khóa đó).
• Đi qua một đường kết nối \(j\) có \(u[j] = x\) hoặc \(v[j] = x\), nếu trước đó đã thu thập được một chìa khóa loại \(c[j]\). Lưu ý rằng người chơi không bao giờ bỏ đi chìa khóa đã thu thập.

Người chơi bắt đầu trò chơi tại một phòng \(s\) mà không mang theo chìa khóa nào. Phòng \(t\) được gọi là có thể đến được từ phòng \(s\) nếu người chơi bắt đầu ở phòng \(s\) có thể thực hiện một dãy hành động như trên để đến phòng \(t\).

Với mỗi phòng \(i\) (\(0 \le i \le n-1\)), gọi \(p[i]\) là số phòng có thể đến được từ phòng \(i\). Timothy muốn biết tập hợp các chỉ số \(i\) đạt giá trị \(p[i]\) nhỏ nhất trong tất cả các chỉ số \(0 \le i \le n-1\).

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u,
                                std::vector<int> v, std::vector<int> c);

• r: mảng độ dài \(n\). Với mỗi \(i\) (\(0 \le i \le n-1\)), chìa khóa trong phòng \(i\) thuộc loại \(r[i]\).
• u, v: hai mảng độ dài \(m\). Với mỗi \(j\) (\(0 \le j \le m-1\)), đường kết nối \(j\) nối hai phòng \(u[j]\) và \(v[j]\).
• c: mảng độ dài \(m\). Với mỗi \(j\) (\(0 \le j \le m-1\)), loại chìa khóa cần để đi qua đường kết nối \(j\) là \(c[j]\).
• Hàm phải trả về mảng \(a\) độ dài \(n\). Với mỗi \(0 \le i \le n-1\), \(a[i]\) phải bằng \(1\) nếu \(p[i] \le p[j]\) với mọi \(j\) thỏa mãn \(0 \le j \le n-1\). Ngược lại, \(a[i]\) phải bằng \(0\).

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): \(n\ m\).
• Dòng \(2\): \(r[0]\ r[1]\ \ldots\ r[n-1]\).
• Dòng \(3+j\) (\(0 \le j \le m-1\)): \(u[j]\ v[j]\ c[j]\).

Dữ liệu ra

Trình chấm mẫu in giá trị trả về của find_reachable theo định dạng sau:

• Dòng \(1\): \(a[0]\ a[1]\ \ldots\ a[n-1]\).

Ràng buộc

• \(2 \le n \le 300\,000\).
• \(1 \le m \le 300\,000\).
• \(0 \le r[i] \le n-1\) với mọi \(0 \le i \le n-1\).
• \(0 \le u[j], v[j] \le n-1\) và \(u[j] \ne v[j]\) với mọi \(0 \le j \le m-1\).
• \(0 \le c[j] \le n-1\) với mọi \(0 \le j \le m-1\).

Phân nhóm

Ví dụ

find_reachable([0, 1, 1, 2],
               [0, 0, 1, 1, 3], [1, 2, 2, 3, 1], [0, 0, 1, 0, 2])

[0, 1, 1, 0]

find_reachable([0, 1, 1, 2, 2, 1, 2],
               [0, 0, 1, 1, 2, 3, 3, 4, 4, 5],
               [1, 2, 2, 3, 3, 4, 5, 5, 6, 6],
               [0, 0, 1, 0, 0, 1, 2, 0, 2, 1])

[0, 1, 1, 0, 1, 0, 1]

find_reachable([0, 0, 0], [0], [1], [0])

[0, 0, 1]

Nguồn

IOI 2021, Ngày 1 — Keys (keys).

Một công viên gần đó có \(n\) đài phun nước, được đánh số từ \(0\) đến \(n-1\). Ta mô hình hóa các đài phun nước bằng các điểm trên mặt phẳng tọa độ hai chiều. Cụ thể, đài phun nước \(i\) (\(0 \le i \le n-1\)) là điểm \((x[i], y[i])\), trong đó \(x[i]\) và \(y[i]\) là các số nguyên chẵn. Vị trí các đài phun nước đôi một khác nhau.

Kiến trúc sư Timothy được thuê để lên kế hoạch xây dựng một số con đường và bố trí một ghế đá cho mỗi con đường. Mỗi con đường là một đoạn thẳng nằm ngang hoặc thẳng đứng, có độ dài \(2\), với hai đầu mút là hai đài phun nước khác nhau. Các con đường phải được xây dựng sao cho có thể đi lại giữa hai đài phun nước bất kỳ bằng cách di chuyển dọc theo các con đường. Ban đầu, công viên không có con đường nào.

Với mỗi con đường, cần đặt đúng một ghế đá trong công viên và gán ghế đá đó cho con đường (nghĩa là ghế quay mặt về phía con đường). Mỗi ghế đá phải được đặt tại một điểm \((a, b)\) sao cho \(a\) và \(b\) là các số nguyên lẻ. Vị trí các ghế đá phải đôi một khác nhau. Một ghế đá tại \((a, b)\) chỉ có thể được gán cho một con đường nếu cả hai đầu mút của con đường đều thuộc tập hợp:

Ví dụ, ghế đá tại \((3,3)\) chỉ có thể được gán cho một con đường là một trong bốn đoạn thẳng \((2,2)\)–\((2,4)\), \((2,4)\)–\((4,4)\), \((4,4)\)–\((4,2)\), \((4,2)\)–\((2,2)\).

Hãy giúp Timothy xác định liệu có thể xây dựng các con đường, đặt và gán các ghế đá thỏa mãn tất cả các điều kiện trên hay không. Nếu có, hãy đưa ra một phương án hợp lệ. Nếu có nhiều phương án thỏa mãn tất cả các điều kiện, bạn có thể đưa ra bất kỳ phương án nào.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

int construct_roads(std::vector<int> x, std::vector<int> y);

• x, y: hai mảng độ dài \(n\). Với mỗi \(i\) (\(0 \le i \le n-1\)), đài phun nước \(i\) là điểm \((x[i], y[i])\), trong đó \(x[i]\) và \(y[i]\) là các số nguyên chẵn.
• Nếu có phương án xây dựng hợp lệ, hàm phải gọi build (xem dưới đây) đúng một lần để báo cáo phương án, sau đó trả về \(1\).
• Nếu không, hàm phải trả về \(0\) mà không gọi build.
• Hàm này được gọi đúng một lần.

Chương trình của bạn có thể gọi hàm sau để đưa ra một phương án xây dựng đường và bố trí ghế đá hợp lệ:

void build(std::vector<int> u, std::vector<int> v,
           std::vector<int> a, std::vector<int> b);

• Gọi \(m\) là tổng số con đường trong phương án xây dựng.
• u, v: hai mảng độ dài \(m\), biểu diễn các con đường cần xây dựng. Các con đường được đánh số từ \(0\) đến \(m-1\). Với mỗi \(j\) (\(0 \le j \le m-1\)), con đường \(j\) nối hai đài phun nước \(u[j]\) và \(v[j]\). Mỗi con đường phải là một đoạn thẳng nằm ngang hoặc thẳng đứng có độ dài \(2\). Hai con đường khác nhau bất kỳ có nhiều nhất một điểm chung (là một đài phun nước). Sau khi xây dựng, phải có thể đi lại giữa hai đài phun nước bất kỳ bằng cách di chuyển dọc theo các con đường.
• a, b: hai mảng độ dài \(m\), biểu diễn các ghế đá. Với mỗi \(j\) (\(0 \le j \le m-1\)), một ghế đá được đặt tại \((a[j], b[j])\) và được gán cho con đường \(j\). Không có hai ghế đá khác nhau nào cùng vị trí.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): \(n\).
• Dòng \(2+i\) (\(0 \le i \le n-1\)): \(x[i]\ y[i]\).

Dữ liệu ra

Trình chấm mẫu in kết quả theo định dạng sau:

• Dòng \(1\): giá trị trả về của construct_roads.

Nếu construct_roads trả về \(1\) và build(u, v, a, b) được gọi, trình chấm mẫu in thêm:

• Dòng \(2\): \(m\).
• Dòng \(3+j\) (\(0 \le j \le m-1\)): \(u[j]\ v[j]\ a[j]\ b[j]\).

Ràng buộc

• \(1 \le n \le 200\,000\).
• \(2 \le x[i], y[i] \le 200\,000\) với mọi \(0 \le i \le n-1\).
• \(x[i]\) và \(y[i]\) là các số nguyên chẵn với mọi \(0 \le i \le n-1\).
• Không có hai đài phun nước nào cùng vị trí.

Phân nhóm

Ví dụ

construct_roads([4, 4, 6, 4, 2], [4, 6, 4, 2, 4])

1

build([0, 0, 3, 4], [2, 1, 0, 0], [5, 3, 5, 3], [5, 5, 3, 3])

build([1, 2, 3, 4], [0, 0, 0, 0], [5, 5, 3, 3], [5, 3, 3, 5])

construct_roads([2, 4], [2, 6])

0

Nguồn

IOI 2021, Ngày 1 — Fountain Parks (parks).