Bài này có đến 50% test mà N <= 100 --> Nếu bạn làm N*log^2 thì ko thể nào TLE các test này được --> bài của bạn bị WA hoặc RE.
1 số chú ý khi post bài:
Bạn cũng có thể tham khảo thêm về cách đặt câu hỏi.
vâng cảm ơn anh em sẽ rút kinh nghiệm :)
Em đã link account VOJ nếu anh rảnh anh có thể check submission dùm em được ko ạ ? Em học tin 2 năm và đã thi quốc gia :)
Em bị WA
Còn tôi làm chặt nhị phân t của [0..max(ti)], sau đó:
Cách 1: dùng số cặp ghép cực đại được 30, chắc LTE.
Cách 2: mỗi t tính Li, Ri, SKNi lần lượt là vị trí xa nhất bên trái, xa nhất bên phải và số vị trí tối đa mà i có thể đến (SKNi = Ri-Li+1). Thời điểm tìm cảnh sát cho cột j, tôi dùng may rủi lấy anh i nào có Li<=j<=Ri và SKNi bé nhất gán cho j, đồng thời giảm SKNi của tất cả các anh có thể đến được j. DPT O(N^2.log(t), được có 30 điểm, vậy chứng tỏ tôi có sai, chắc ở đoạn may rủi. Làm ơn bạn nào gợi ý cho. ID: 15198612
Xin cảm ơn.
Độ phức tạp AC là O(NlogN*log(maxT)). ĐOạn kiểm tra O(NlogN) thì AC được.
Thuật toán của bạn chưa đúng!
Bạn có thể tham khảo thuật toán và code tại: http://yeulaptrinh.pw/48/spoj-move12/