CCO-25 (2025) - 4 (Restaurant Recommendation Rescue)

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Blockly, C, C++, Java, Pascal, Python

Restaurant Recommendation Rescue

Μια επίδοξη μουσικός, η K, λατρεύει να πηγαίνει για shabu-shabu! Πρόσφατα, έχει επισκεφθεί N εστιατόρια shabu-shabu, αριθμημένα από 1 έως N, ακολουθώντας τον παρακάτω αλγόριθμο:

  1. Η K διατηρεί μια διατεταγμένη λίστα προτάσεων, η οποία αρχικά περιέχει το εστιατόριο 1.
  2. Την i-οστή ημέρα, επισκέπτεται το επόμενο προτεινόμενο εστιατόριο στη λίστα της, το οποίο της προτείνει τα εστιατόρια R_i = \{r_{i,1}, \ldots, r_{i,\ell_i}\}.
  3. Η K προσθέτει το R_i στη λίστα των εστιατορίων που θα επισκεφθεί.
  4. Η K επαναλαμβάνει τα βήματα 2 - 4 μέχρι να εξαντληθούν τα προτεινόμενα εστιατόρια.
  5. Η K καταγράφει τον πίνακα A_0, \ldots, A_{N-1}, όπου το A_i ισούται με τον αριθμό των εστιατορίων που της προτάθηκαν την (i+1)-οστή ημέρα. Δηλαδή, A_i = |R_{i+1}|.

Εγγυάται ότι \bigcup_{i=1}^{N} R_i = \{2, \ldots, N\} και ότι R_i \cap R_j = \emptyset για i \ne j, δηλαδή κάθε εστιατόριο, εκτός από το πρώτο, θα προταθεί από ακριβώς ένα άλλο εστιατόριο.

Μόλις η K ολοκληρώσει τη λίστα της, ο φίλος της H, που του αρέσει να κάνει φάρσες, αποφασίζει να της παίξει μια φάρσα! Αντικαθιστά τον πίνακα A_0, ..., A_{N-1} με έναν άλλο πίνακα B_0, ..., B_{N-1}. Η K πιστεύει ότι αυτός ο νέος πίνακας B_i μπορεί απλώς να είναι μια κυκλική μετατόπιση του αρχικού της πίνακα, γι' αυτό σας ζητά να προσδιορίσετε όλες τις δυνατές τιμές 0 \le k < N για τις οποίες ισχύει A_i = B_{(i+k) \bmod N}, για κάθε 0 \le i < N, για οποιαδήποτε έγκυρη έξοδο του αλγορίθμου της, A_0, \ldots, A_{N-1}.

Επιπλέον, η K θα εκτελέσει στη συνέχεια Q πράξεις. Σε κάθε i-οστή πράξη, ανταλλάσσει τα B_{x_i} και B_{y_i} και σας ζητά να κάνετε το ίδιο στον νέο πίνακα. Μπορείτε να βοηθήσετε την K να καταλάβει τη φάρσα του φίλου της;

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει δύο ακέραιους αριθμούς, N (1 \le N \le 500.000) και Q (0 \le Q \le 300.000).

Η επόμενη γραμμή θα περιέχει N μη αρνητικούς ακέραιους αριθμούς, χωρισμένους με κενά, B_0, B_1, \ldots, B_{N-1} (0 \le B_i < N), που αποτελούν την αρχική ακολουθία.

Η i-οστή από τις επόμενες Q γραμμές θα περιέχει δύο ακέραιους αριθμούς, x_i και y_i (0 \le x_i, y_i < N και x_i \ne y_i), οι οποίοι υποδεικνύουν ότι πρέπει να ανταλλάξετε τα B_{x_i} και B_{y_i}.

Ο παρακάτω πίνακας δείχνει πώς κατανέμονται οι 25 διαθέσιμοι βαθμοί:

 Βαθμοί  Περιορισμοί Επιπλέον περιορισμοί
3 1 \le N \le 8 Q = 0
7 1 \le N \le 5000 Q = 0
10 1 \le N \le 500.000 Q = 0
5 1 \le N \le 500.000 0 \le Q \le 300.000
Έξοδος

Για καθέναν από τους Q+1 πίνακες (συμπεριλαμβανομένου του αρχικού πίνακα B_0, \ldots, B_{N-1}), έστω S = \{k_1, \ldots, k_m\} το σύνολο των ακεραίων 0 \le k_j < N για τους οποίους υπάρχει μια έγκυρη έξοδος A_0, \ldots, A_{N-1} του αλγορίθμου της K, τέτοια ώστε A_i = B_{(i+k_j) \bmod N} για κάθε 0 \le i < N.

Εκτυπώστε σε μία γραμμή τους ακέραιους αριθμούς m και \sum_{i=1}^{m} k_i \bmod (998\,244\,353), χωρισμένους με ένα κενό.

Ειδικότερα, αν S = \emptyset, η έξοδός σας θα πρέπει να είναι 0 0.

Παράδειγμα

input

5 3
1 2 0 0 1
0 2
1 3
3 2

output

1 4
1 1
1 2
1 2
Επεξήγηση του παραδείγματος

Ο πίνακας A είναι [1, 1, 2, 0, 0]. Μπορεί να αποδειχθεί ότι αυτή είναι η μοναδική έγκυρη έξοδος του αλγορίθμου της K που αντιστοιχεί στον πίνακα B = [1, 2, 0, 0, 1]. Μια πιθανή είσοδος για τον αλγόριθμο της K που παράγει αυτόν τον πίνακα A είναι:

R_1 = \{2\}
R_2 = \{3\}
R_3 = \{4, 5\}
R_4 = \emptyset
R_5 = \emptyset

Μετά την ανταλλαγή των B_0 και B_2, προκύπτει ο πίνακας:

B = [0, 2, 1, 0, 1].

Μπορεί να αποδειχθεί ότι η μοναδική έγκυρη έξοδος του αλγορίθμου της K που αντιστοιχεί σε αυτόν τον πίνακα είναι

A = [2, 1, 0, 1, 0].

Μια πιθανή είσοδος για τον αλγόριθμο της K που παράγει αυτόν τον πίνακα A είναι:

R_1 = \{2, 3\}
R_2 = \{4\}
R_3 = \emptyset
R_4 = \{5\}
R_5 = \emptyset

Comments

There are no comments at the moment.