Submission details
Task:Train schedule
Sender:aalto25e_006
Submission time:2025-10-01 18:46:12 +0300
Language:Python3 (PyPy3)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.04 sdetails
#20.04 sdetails
#30.04 sdetails
#40.04 sdetails
#5ACCEPTED0.04 sdetails
#60.04 sdetails
#70.04 sdetails
#80.04 sdetails
#90.04 sdetails
#100.04 sdetails
#110.04 sdetails
#120.04 sdetails
#130.04 sdetails
#140.04 sdetails
#150.04 sdetails
#160.04 sdetails
#170.04 sdetails
#180.04 sdetails
#19ACCEPTED0.04 sdetails
#200.04 sdetails
#21ACCEPTED0.04 sdetails
#220.04 sdetails
#230.04 sdetails
#240.04 sdetails
#250.04 sdetails
#260.04 sdetails
#270.04 sdetails
#280.04 sdetails
#290.04 sdetails
#300.04 sdetails
#310.04 sdetails
#320.04 sdetails
#330.04 sdetails
#340.04 sdetails
#350.04 sdetails
#360.04 sdetails
#370.04 sdetails
#380.04 sdetails
#390.04 sdetails
#400.04 sdetails
#410.05 sdetails
#420.05 sdetails
#430.05 sdetails
#440.05 sdetails
#450.05 sdetails
#460.05 sdetails
#470.05 sdetails
#480.05 sdetails
#490.05 sdetails
#500.05 sdetails
#510.05 sdetails
#520.05 sdetails
#530.05 sdetails
#540.05 sdetails
#550.06 sdetails
#560.06 sdetails
#570.06 sdetails
#580.06 sdetails
#590.06 sdetails
#600.06 sdetails
#610.95 sdetails
#620.95 sdetails
#630.95 sdetails
#640.95 sdetails
#650.97 sdetails
#660.97 sdetails
#670.97 sdetails
#680.96 sdetails
#690.97 sdetails
#700.97 sdetails
#710.93 sdetails
#720.98 sdetails

Code

"""n = int(input())
trains = list(map(int, input().split()))
result = [1] * n
precompute = set()


addMultiple = 0
for i in range(n):
    if trains[i] not in precompute:
        for j in range(i + 1, n):
            if (i + (j - i) * trains[i]) >= n:
                break
            if trains[i] == trains[j] and j < i == j - trains[i] and trains[i]:
                addMultiple += 1
                precompute.add(trains[i])
            result[i + (j - i) * trains[i]] += 1 + addMultiple


print(*result)"""

n = int(input())
trains = list(map(int, input().split()))
result = [0] * n
sqrt_n = int(n ** 0.5) + 1

# Handle small step sizes (≤ sqrt(n))
for step in range(1, min(sqrt_n + 1, n + 1)):
    count = 0
    for i in range(n):
        if trains[i] == step:
            count += 1
        result[i] += count
        if (i + 1) % step == 0:  # Reset after each complete cycle
            count = 0

# Handle large step sizes (> sqrt(n))
for i in range(n):
    if trains[i] > sqrt_n:
        pos = i
        count = 0
        while pos < n:
            if trains[pos] == trains[i]:
                count += 1
            result[pos] += count
            pos += trains[i]

print(*result)

Test details

Test 1

Verdict: ACCEPTED

input
1

correct output

user output
1

Test 2

Verdict:

input
2
2 2 

correct output
1 1 

user output
1 2

Test 3

Verdict:

input
2
2 1 

correct output
1 1 

user output
1 2

Test 4

Verdict:

input
3
2 2 3 

correct output
1 1 2 

user output
1 2 1

Test 5

Verdict: ACCEPTED

input
3
3 2 1 

correct output
1 1 1 

user output
1 1 1

Test 6

Verdict:

input
3
1 2 1 

correct output
1 2 2 

user output
1 1 1

Test 7

Verdict:

input
4
2 3 1 3 

correct output
1 1 2 2 

user output
1 2 2 1

Test 8

Verdict:

input
4
2 3 1 1 

correct output
1 1 2 2 

user output
1 2 2 1

Test 9

Verdict:

input
4
3 2 2 4 

correct output
1 1 1 3 

user output
1 2 2 2

Test 10

Verdict:

input
4
2 1 3 3 

correct output
1 1 3 2 

user output
1 2 1 1

Test 11

Verdict:

input
5
3 4 5 4 5 

correct output
1 1 1 2 1 

user output
1 2 2 1 1

Test 12

Verdict:

input
5
5 4 5 1 1 

correct output
1 1 1 1 2 

user output
1 1 1 1 1

Test 13

Verdict:

input
5
1 1 5 3 5 

correct output
1 2 3 3 3 

user output
1 1 1 1 2

Test 14

Verdict:

input
5
1 4 5 2 1 

correct output
1 2 2 2 2 

user output
1 1 1 1 1

Test 15

Verdict:

input
5
3 5 4 4 2 

correct output
1 1 1 2 1 

user output
1 2 2 1 1

Test 16

Verdict:

input
5
1 5 5 2 2 

correct output
1 2 2 2 2 

user output
1 1 1 1 1

Test 17

Verdict:

input
5
2 5 1 1 3 

correct output
1 1 2 2 4 

user output
1 2 1 1 1

Test 18

Verdict:

input
5
2 4 2 3 5 

correct output
1 1 2 1 3 

user output
1 2 1 2 2

Test 19

Verdict: ACCEPTED

input
5
5 5 3 2 1 

correct output
1 1 1 1 1 

user output
1 1 1 1 1

Test 20

Verdict:

input
5
2 3 3 3 1 

correct output
1 1 2 1 3 

user output
1 2 2 1 2

Test 21

Verdict: ACCEPTED

input
10
6 8 9 7 9 6 9 5 7 7 

correct output
1 1 1 1 1 1 2 1 1 2 

user output
1 1 1 1 1 1 2 1 1 2

Test 22

Verdict:

input
10
10 8 10 1 2 4 10 2 3 1 

correct output
1 1 1 1 2 2 3 2 3 5 

user output
1 1 1 1 1 2 2 2 1 2

Test 23

Verdict:

input
10
2 1 10 6 10 5 5 5 4 4 

correct output
1 1 3 2 3 2 3 2 3 3 

user output
1 2 1 1 1 1 1 1 1 3

Test 24

Verdict:

input
10
1 8 9 3 2 6 6 9 5 9 

correct output
1 2 2 2 2 2 4 2 3 4 

user output
1 1 1 1 2 3 1 1 1 2

Test 25

Verdict:

input
10
6 10 8 7 3 10 1 3 5 8 

correct output
1 1 1 1 1 1 2 3 2 2 

user output
1 1 1 1 1 2 2 1 2 1

Test 26

Verdict:

input
10
1 9 9 3 4 10 10 5 1 7 

correct output
1 2 2 2 2 2 3 2 3 4 

user output
1 1 1 1 2 3 2 2 1 1

Test 27

Verdict:

input
10
4 9 1 2 6 6 5 4 7 5 

correct output
1 1 1 2 3 3 2 3 3 3 

user output
1 2 2 2 1 1 1 1 1 1

Test 28

Verdict:

input
10
3 8 4 5 10 8 5 10 4 6 

correct output
1 1 1 2 1 1 3 1 2 3 

user output
1 2 2 2 1 1 1 1 2 3

Test 29

Verdict:

input
10
10 9 6 3 1 5 5 6 5 6 

correct output
1 1 1 1 1 2 3 2 3 3 

user output
1 1 1 1 2 2 1 1 2 1

Test 30

Verdict:

input
10
4 6 5 5 1 2 4 2 1 3 

correct output
1 1 1 1 2 2 2 5 4 5 

user output
1 2 2 2 1 1 1 4 2 1

Test 31

Verdict:

input
100
12 15 17 13 18 11 17 9 13 13 8...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 ...

user output
1 1 1 1 1 1 2 2 3 2 2 2 4 4 4 ...

Test 32

Verdict:

input
100
20 15 19 1 3 7 20 3 5 2 8 4 8 ...

correct output
1 1 1 1 2 2 2 3 2 2 4 3 3 6 2 ...

user output
1 1 1 1 1 2 2 1 2 2 1 2 2 3 3 ...

Test 33

Verdict:

input
100
4 1 19 11 19 9 10 9 7 7 4 5 14...

correct output
1 1 2 2 3 2 2 2 3 2 2 2 3 2 5 ...

user output
1 2 2 2 2 2 3 4 5 4 4 4 4 4 2 ...

Test 34

Verdict:

input
100
2 15 17 6 3 11 12 18 9 18 1 3 ...

correct output
1 1 2 1 2 1 2 2 2 2 3 2 3 4 5 ...

user output
1 2 1 1 2 3 2 2 2 2 2 1 1 1 2 ...

Test 35

Verdict:

input
100
11 98 15 14 5 98 1 6 9 16 20 1...

correct output
1 1 1 1 1 1 1 2 2 3 2 3 2 3 3 ...

user output
1 2 2 2 2 2 2 2 3 3 3 2 1 1 2 ...

Test 36

Verdict:

input
100
6 88 84 21 37 92 98 49 9 62 40...

correct output
1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 ...

user output
1 2 2 2 2 2 1 1 1 1 1 1 1 1 1 ...

Test 37

Verdict:

input
100
7 83 5 11 12 53 9 7 63 9 15 52...

correct output
1 1 1 1 1 1 1 3 1 1 1 1 2 1 4 ...

user output
1 2 2 3 4 3 3 3 4 3 4 3 3 3 2 ...

Test 38

Verdict:

input
100
23 78 32 44 98 73 46 98 31 54 ...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 ...

Test 39

Verdict:

input
100
97 87 54 5 2 9 9 53 10 12 55 1...

correct output
1 1 1 1 1 1 2 1 3 1 2 1 2 2 3 ...

user output
1 1 1 1 2 2 2 3 3 2 1 1 1 1 1 ...

Test 40

Verdict:

input
100
37 51 50 50 1 14 32 15 2 22 88...

correct output
1 1 1 1 1 2 2 2 2 2 3 2 3 2 3 ...

user output
1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 ...

Test 41

Verdict:

input
200
12 15 17 13 18 11 17 9 13 13 8...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 ...

user output
1 2 3 3 4 4 5 5 6 6 7 7 7 5 5 ...

Test 42

Verdict:

input
200
20 15 19 1 3 7 20 3 5 2 8 4 8 ...

correct output
1 1 1 1 2 2 2 3 2 2 4 3 3 6 2 ...

user output
1 1 2 2 2 3 3 2 3 3 2 3 3 4 4 ...

Test 43

Verdict:

input
200
4 1 19 11 19 9 10 9 7 7 4 5 14...

correct output
1 1 2 2 3 2 2 2 3 2 2 2 3 2 5 ...

user output
1 2 2 2 2 2 3 4 5 4 4 4 4 5 3 ...

Test 44

Verdict:

input
200
2 15 17 6 3 11 12 18 9 18 1 3 ...

correct output
1 1 2 1 2 1 2 2 2 2 3 2 3 4 5 ...

user output
1 2 2 2 3 4 3 4 4 4 4 3 2 2 3 ...

Test 45

Verdict:

input
200
11 195 15 14 5 196 2 6 9 16 40...

correct output
1 1 1 1 1 1 1 1 2 2 2 2 2 2 3 ...

user output
1 2 2 3 4 4 4 5 5 5 5 4 3 3 3 ...

Test 46

Verdict:

input
200
12 175 167 42 73 184 196 98 18...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 ...

user output
1 2 2 2 2 2 2 2 2 2 2 2 1 1 1 ...

Test 47

Verdict:

input
200
7 165 9 22 12 106 9 7 125 9 15...

correct output
1 1 1 1 1 1 1 2 1 1 1 2 1 1 3 ...

user output
1 2 2 3 3 4 4 4 5 3 4 5 4 4 3 ...

Test 48

Verdict:

input
200
46 156 64 88 196 145 92 196 62...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 ...

Test 49

Verdict:

input
200
194 174 107 5 3 9 9 105 10 12 ...

correct output
1 1 1 1 1 1 1 2 2 1 2 1 1 3 2 ...

user output
1 1 1 1 2 2 2 3 3 2 2 2 1 1 2 ...

Test 50

Verdict:

input
200
73 101 100 100 2 27 64 29 3 44...

correct output
1 1 1 1 1 1 2 1 2 1 2 2 2 1 3 ...

user output
1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 ...

Test 51

Verdict:

input
1000
12 15 17 13 18 11 17 9 13 13 8...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 ...

user output
1 2 3 4 5 6 7 8 9 9 10 10 10 8...

Test 52

Verdict:

input
1000
20 15 19 1 3 7 20 3 5 2 8 4 8 ...

correct output
1 1 1 1 2 2 2 3 2 2 4 3 3 6 2 ...

user output
1 2 3 4 4 5 5 5 6 6 5 6 6 7 7 ...

Test 53

Verdict:

input
1000
4 1 19 11 19 9 10 9 7 7 4 5 14...

correct output
1 1 2 2 3 2 2 2 3 2 2 2 3 2 5 ...

user output
1 2 2 3 3 4 5 6 7 6 6 6 6 7 5 ...

Test 54

Verdict:

input
1000
2 15 17 6 3 11 12 18 9 18 1 3 ...

correct output
1 1 2 1 2 1 2 2 2 2 3 2 3 4 5 ...

user output
1 2 2 3 4 5 4 5 6 6 7 6 5 5 6 ...

Test 55

Verdict:

input
1000
11 973 15 14 5 977 7 6 9 16 19...

correct output
1 1 1 1 1 1 1 1 1 2 1 2 1 3 2 ...

user output
1 2 2 3 4 4 4 4 5 5 6 5 5 5 5 ...

Test 56

Verdict:

input
1000
56 871 832 207 364 919 980 489...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

Test 57

Verdict:

input
1000
7 822 42 108 12 530 9 7 623 9 ...

correct output
1 1 1 1 1 1 1 2 1 1 1 1 1 1 3 ...

user output
1 2 2 2 2 3 3 3 4 3 4 5 4 4 3 ...

Test 58

Verdict:

input
1000
228 780 319 439 979 724 456 97...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

Test 59

Verdict:

input
1000
969 870 531 5 12 9 9 523 10 12...

correct output
1 1 1 1 1 1 1 1 2 1 1 1 1 2 2 ...

user output
1 1 1 1 2 2 3 4 4 3 3 3 2 2 3 ...

Test 60

Verdict:

input
1000
365 502 500 496 8 134 317 143 ...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 ...

user output
1 1 1 1 1 2 2 2 1 2 2 2 2 2 1 ...

Test 61

Verdict:

input
100000
12 15 17 13 18 11 17 9 13 13 8...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 ...

user output
1 2 3 4 5 6 7 8 9 9 10 10 10 8...

Test 62

Verdict:

input
100000
20 15 19 1 3 7 20 3 5 2 8 4 8 ...

correct output
1 1 1 1 2 2 2 3 2 2 4 3 3 6 2 ...

user output
1 2 3 4 4 5 5 5 6 6 5 6 6 7 7 ...

Test 63

Verdict:

input
100000
4 1 19 11 19 9 10 9 7 7 4 5 14...

correct output
1 1 2 2 3 2 2 2 3 2 2 2 3 2 5 ...

user output
1 2 2 3 3 4 5 6 7 6 6 6 6 7 5 ...

Test 64

Verdict:

input
100000
2 15 17 6 3 11 12 18 9 18 1 3 ...

correct output
1 1 2 1 2 1 2 2 2 2 3 2 3 4 5 ...

user output
1 2 2 3 4 5 4 5 6 6 7 6 5 5 6 ...

Test 65

Verdict:

input
100000
11 97270 15 14 5 97629 624 6 9...

correct output
1 1 1 1 1 1 1 1 1 2 1 2 1 2 2 ...

user output
1 2 2 3 4 4 4 4 5 5 6 5 5 5 5 ...

Test 66

Verdict:

input
100000
5519 87075 83135 20673 36375 9...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

Test 67

Verdict:

input
100000
7 82125 4170 10766 12 52983 9 ...

correct output
1 1 1 1 1 1 1 2 1 1 1 1 1 1 3 ...

user output
1 2 2 2 2 3 3 3 4 3 4 5 4 4 3 ...

Test 68

Verdict:

input
100000
22735 77994 31898 43842 97824 ...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

Test 69

Verdict:

input
100000
96856 86921 53087 5 1140 9 9 5...

correct output
1 1 1 1 1 1 1 1 2 1 1 1 1 2 2 ...

user output
1 1 1 1 2 1 2 3 3 2 2 2 2 2 3 ...

Test 70

Verdict:

input
100000
36447 50189 49914 49579 755 13...

correct output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

Test 71

Verdict:

input
100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

Test 72

Verdict:

input
100000
1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 ...

correct output
1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 ...

user output
1 1 1 2 2 3 1 2 1 2 3 4 3 4 5 ...