3729 - Exclusiv
Enunt
Se consideră doi vectori care conțin numere naturale: s cu M elemente și v cu N elemente. Numim secvență i-exclusivă o secvență a vectorului s care nu conține niciuna dintre valorile v[1], v[2], …, v[i].
Cerinţa
Scrieți un program care să determine, pentru orice 1 ≤ i ≤ N, lungimea maximă a unei secvențe i-exclusive.
Date de intrare
Fișierul de intrare exclusiv.in conține pe prima linie numerele naturale M și N. Pe linia a doua se află M numere naturale reprezentând elementele vectorului s, iar pe linia a treia N numere naturale reprezentând elementele vectorului v. Valorile scrise pe aceeași linie sunt separate prin câte un spațiu.
Date de ieșire
Fișierul de ieșire exclusiv.out va conține N linii. Pe linia i (1 ≤ i ≤ N) va fi scris un număr natural care reprezintă lungimea maximă a unei secvențe i-exclusive.
Restricţii şi precizări
- 1 ≤ N ≤ 2.000
- 3 ≤ M ≤ 100.000
- Vectorii s și v conțin numere naturale mai mici sau egale cu 2.000.000.000, memorate începând cu poziția 1
- Valorile din fiecare vector nu sunt obligatoriu distincte două câte două.
- O subsecvență nevidă în s este formată din elemente situate pe poziții consecutive (s[i], s[i + 1], …, s[j]), i ≤ j. O subsecvență i-exclusivă poate fi și vidă, lungimea ei fiind 0.
Exemplu
- exclusiv.in
20 6 11 5 11 7 2 10 11 9 2 77 88 88 88 2 7 2 2 77 2 11 11 5 7 9 5 2
- exclusiv.out
12 12 7 6 6 4
Explicație
Cea mai lungă secvență 1-exclusivă (care nu conține valoarea 11) este 9 2 77 88 88 88 2 7 2 2 77 2 și are lungimea 12. Cea mai lungă secvență 2-exclusivă (care nu conține valorile 11 și 5) este 9 2 77 88 88 88 2 7 2 2 77 2 și are lungimea 12. Cea mai lungă secvență 3-exclusivă (care nu conține valorile 11, 5 și 7) este 9 2 77 88 88 88 2 și are lungimea 7. Cea mai lungă secvență 4-exclusivă (care nu conține valorile 11, 5, 7 și 9) este 2 77 88 88 88 2 și are lungimea 6. Cea mai lungă secvență 5-exclusivă (care nu conține valorile 11, 5 7, 9 și 5) este 2 77 88 88 88 2 și are lungimea 6. Cea mai lungă secvență 6-exclusivă (care nu conține valorile 11, 5, 7, 9, 5 și 2) este 77 88 88 88 și are lungimea 4.
Rezolvare
def longest_exclusive_sequence(s, v):
last_position = {value: -1 for value in v}
longest_sequence = 0
current_sequence = 0
for value in s:
if value in last_position:
current_sequence = min(current_sequence + 1, 1 + last_position[value])
else:
current_sequence += 1
last_position[value] = current_sequence
longest_sequence = max(longest_sequence, current_sequence)
return longest_sequence
def main():
M, N = map(int, input().split())
s = list(map(int, input().split()))
v = list(map(int, input().split()))
result = []
for i in range(N):
result.append(longest_exclusive_sequence(s, v[:i+1]))
for length in result:
print(length)
if __name__ == "__main__":
main()