Có \(N\) học sinh trong một lớp. Mỗi học sinh được đánh số từ \(0\) đến \(N-1\) theo thứ hạng hiện tại trong lớp: học sinh \(i\) đang có hạng \(i\). Hạng \(0\) là tốt nhất và hạng \(N-1\) là thấp nhất.

Lớp vừa tổ chức hai kỳ thi Tiếng Anh và Toán. Học sinh \(i\) đạt hạng \(A[i]\) trong kỳ thi Tiếng Anh và hạng \(B[i]\) trong kỳ thi Toán. Cả \(A\) và \(B\) đều là các hoán vị độ dài \(N\).

Trong bài này, một hoán vị \(P\) độ dài \(N\) là một mảng thỏa mãn \(0\le P[i]\le N-1\) với mọi \(0\le i<N\), và \(P[i]\ne P[j]\) với mọi \(0\le i<j<N\). Chẳng hạn, \([2,1,0]\) là một hoán vị độ dài \(3\), còn \([1,2,3]\) và \([2,0,2]\) thì không.

Giáo viên muốn xếp hạng lại các học sinh. Thứ hạng mới được biểu diễn bởi một hoán vị \(P\). Với mỗi học sinh \(i\), thứ hạng mới phải thỏa mãn ít nhất một trong hai điều kiện sau:

• Với mọi \(j\) sao cho \(P[j]<P[i]\), học sinh \(j\) có hạng Tiếng Anh tốt hơn học sinh \(i\), tức là \(A[j]<A[i]\); hoặc
• Với mọi \(j\) sao cho \(P[j]<P[i]\), học sinh \(j\) có hạng Toán tốt hơn học sinh \(i\), tức là \(B[j]<B[i]\).

Lưu ý rằng điều kiện chỉ áp dụng cho các học sinh \(j\) có \(P[j]<P[i]\); không có ràng buộc nào đối với các học sinh có \(P[j]\ge P[i]\). Khi kiểm tra điều kiện cho một học sinh \(i\), phải chọn một môn duy nhất rồi so sánh với tất cả các học sinh \(j\) tương ứng; không được đổi môn giữa các học sinh \(j\) khác nhau.

Mức độ bất mãn của thứ hạng mới là mức tụt hạng lớn nhất trong số tất cả học sinh, tức là

Các giá trị \(i-P[i]\) không ảnh hưởng đến mức độ bất mãn.

Hãy tìm mức độ bất mãn nhỏ nhất có thể của thứ hạng mới.

Yêu cầu cài đặt

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

int minimum_dissatisfaction(int N, std::vector<int> A,
                            std::vector<int> B);

• \(N\) là số học sinh.
• \(A\) là mảng độ dài \(N\) mô tả thứ hạng trong kỳ thi Tiếng Anh.
• \(B\) là mảng độ dài \(N\) mô tả thứ hạng trong kỳ thi Toán.
• Hàm phải trả về mức độ bất mãn nhỏ nhất có thể.
• Trình chấm gọi hàm này đúng một lần.

Bài nộp không được cài đặt hàm main và phải khai báo #include "exam.h".

Giới hạn

• \(1\le N\le 5\,000\,000\).
• \(0\le A[i],B[i]\le N-1\) với mọi \(0\le i<N\).
• \(A[i]\ne A[j]\) và \(B[i]\ne B[j]\) với mọi \(0\le i<j<N\).

Chấm điểm

Trong phần 8, riêng trình chấm được đảm bảo sử dụng \(1500\) ms trong giới hạn thời gian \(3000\) ms.

Ví dụ

Xét lời gọi:

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

Một cách xếp hạng mới là \(P=[0,2,3,4,1]\).

• Với học sinh \(1\), \(P[1]=2\). Mọi học sinh \(j\) có \(P[j]<P[1]\) đều có hạng Toán tốt hơn học sinh \(1\).
• Với học sinh \(2\), \(P[2]=3\). Mọi học sinh \(j\) có \(P[j]<P[2]\) đều có hạng Tiếng Anh tốt hơn học sinh \(2\).
• Có thể kiểm tra rằng các học sinh còn lại cũng thỏa mãn điều kiện.

Mức độ bất mãn của thứ hạng này là \(1\), và không tồn tại thứ hạng hợp lệ nào có mức độ bất mãn nhỏ hơn. Vì vậy hàm phải trả về 1.

Trình chấm mẫu

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

N
A[0] A[1] ... A[N - 1]
B[0] B[1] ... B[N - 1]

và in một số nguyên là giá trị trả về của minimum_dissatisfaction.

Nguồn: Southeast Asia Team Selection Test 2026, Ngày 1, bài Two Exams.