0610 - Spion

Într-un loc îndepărtat amplasat strategic, se află mai mulţi soldați identificaţi prin numere naturale nenule unice. Ordinea și disciplina militară impun aşezarea soldaților în linie la apelul de dimineață. Fiecare soldat a primit la sosirea în unitate numărul său și numerele de identificare ale camarazilor care trebuie să fie în stânga și în dreapta sa la aliniere. Excepţie fac doi soldaţi santinele care primesc doar numărul propriu de identificare şi se vor aşeza pe prima, respectiv pe ultima poziţie din linie. Uneori, unii soldaţi sunt plecați în misiuni, iar apelul de dimineaţă în unitate se face astfel: fiecare dintre cei prezenţi strigă cele trei numere primite – numărul lui, numărul camaradului din stânga lui şi al camaradului din dreapta lui, chiar dacă aceștia lipsesc.

Ei nu ştiu însă că, după un zid, stă pitită spioana Bulbuka, trimisă în recunoaștere. Ea îi ascultă şi înregistrează toate tripletele de numere care sunt strigate. După cele trei numere strigate de fiecare soldat, Bulbuka, fiind foarte inteligentă, deduce corect câte grupuri de soldaţi care și-au strigat prezența sunt până în momentul respectiv. Ea consideră că un grup este format din toţi acei soldaţi care şi-au strigat propriul număr şi care sunt aşezaţi unul lângă celălalt (dacă un soldat a strigat numărul camaradului, acesta din urmă nu este inclus în grup decât dacă a strigat şi el propriul număr).

Cerința

Aflați care sunt numerele de grupuri de soldați deduse de Bulbuka în fiecare moment.

Date de intrare

Pe prima linie a fişierului input.txt se află N, numărul de soldaţi ce îşi vor striga prezența. Pe următoarele N linii se află câte 3 numere x[i], s[i] și d[i], separate prin câte un spaţiu, reprezentând tripletele pe care le strigă fiecare soldat (x[i] numărul soldatului, s[i] numărul camaradului din stânga lui şi d[i] numărul camaradului din dreapta lui).

Date de ieșire

Fişierul de ieşire output.txt va conţine N linii. Pe fiecare dintre cele N linii se va scrie numărul de grupuri dedus de Bulbuka la momentul respectiv.

Restricții și precizări

• 1 < N < 500000

Exemplul 1

input.txt:

6

9 2 3

8 5 4

5 3 8

7 1 2

2 7 9

3 9 5

output.txt:

1

2

2

3

2

1

Explicație:

Prima dată strigă soldatul 9 care e notat prezent, deci primul grup este format doar din el. Camarazii 2 și 3 ar trebui să fie în stânga și dreapta lui dar nu și-au strigat prezența încă. În consecință, nu fac parte în acest moment din grupul lui 9.

Strigă soldatul 8, se formează două grupuri: {9} și {8}.

Strigă 5, el va intra în grupul lui 8, deci vor fi tot două grupuri: {9} și {8,5}.

Strigă 7, dar pentru că cei doi camarazi nu s-au strigat încă prezenţi, 7 va forma un grup singur. Vor fi acum trei grupuri: {7}, {9} și @{8,5} etc.

Exemplul 2

input.txt:

9999999999

9 2 3

8 5 4

5 3 8

7 1 2

2 7 9

3 9 5

Output:

Input-ul nu convine conditiilor

Rezolvare

<syntaxhighlight lang="python3" line="1"> NMAX = 1600000

def verificare(n):

   if not(2<=n<500000):
       print("Input-ul nu convine conditiilor")
       exit()

n = 0 grupuri = 0

soldati = [0] * ((NMAX + 31) // 32)

def bindex(b):

   return b // 32

def boffset(b):

   return b % 32

def set_bit(b):

   soldati[bindex(b)] |= 1 << boffset(b)

def get_bit(b):

   return (soldati[bindex(b)] & (1 << boffset(b))) != 0

with open("input.txt", "rt") as infile, open("output.txt", "wt") as outfile:

   n = int(infile.readline())
   verificare(n)
   for _ in range(n):
       x, s, d = map(int, infile.readline().split())

       prezenta = get_bit(s) + get_bit(d)
       grupuri += 1 - prezenta

       outfile.write(f"{grupuri}\n")

       set_bit(x)

</syntaxhighlight>