Editing 0610 - Spion (section)

= Restricții și precizări =

* <code>1 < N  < 500000</code>

== 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 <code>9</code> care e notat prezent, deci primul grup este format doar din el. Camarazii <code>2</code> și <code>3</code> 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 <code>9</code>.

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

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

Strigă <code>7</code>, dar pentru că cei doi camarazi nu s-au strigat încă prezenţi, <code>7</code> va forma un grup singur. Vor fi acum trei grupuri: <code>{7}</code>, <code>{9}</code> ș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>