Nene vs. Monsters (Easy Version) (Codeforces 1956E1)
Tags: Math, brute force

This is the easy version of the problem. The only difference between the versions is the constraints on $$$a_i$$$. You can make hacks only if both versions of the problem are solved.Nene is fighting with $$$n$$$ monsters, located in a circle. These monsters are numbered from $$$1$$$ to $$$n$$$, and the $$$i$$$-th ($$$1 \le i \le n$$$) monster's current energy level is $$$a_i$$$.Since the monsters are too strong, Nene decided to fight with them using the Attack Your Neighbour spell. When Nene uses this spell, the following actions happen in the following order one by one:   The $$$1$$$-st monster attacks the $$$2$$$-nd monster;  The $$$2$$$-nd monster attacks the $$$3$$$-rd monster;  $$$\ldots$$$  The $$$(n-1)$$$-th monster attacks the $$$n$$$-th monster;  The $$$n$$$-th monster attacks the $$$1$$$-st monster. When the monster with energy level $$$x$$$ attacks the monster with the energy level $$$y$$$, the energy level of the defending monster becomes $$$\max(0, y-x)$$$ (the energy level of the attacking monster remains equal to $$$x$$$).Nene is going to use this spell $$$10^{100}$$$ times and deal with the monsters that will still have a non-zero energy level herself. She wants you to determine which monsters will have a non-zero energy level once she will use the described spell $$$10^{100}$$$ times.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of test cases follows.The first line contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of monsters.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$) — the current energy levels of monsters.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case,   in the first line output an integer $$$m$$$ — the number of monsters with non-zero energy level after $$$10^{100}$$$ uses of the spell;  in the second line of output $$$m$$$ integers $$$i_1,i_2,\ldots,i_m$$$ ($$$1 \le i_1 < i_2 < \ldots < i_m \le n$$$) — the indices of these monsters in the increasing order. If $$$m=0$$$, you may either output an empty line or don't output it.

Note: In the first test case, the following actions happen during the first $$$3$$$ uses of the spell in this order:  Nene uses the Attack Your Neighbour spell for the first time;  the $$$1$$$-st monster attacks the $$$2$$$-nd monster, after the attack the energy level of the $$$2$$$-nd monster becomes equal to $$$\max(0, 5-2)=3$$$;  the $$$2$$$-nd monster attacks the $$$3$$$-rd monster, after the attack the energy level of the $$$3$$$-rd monster becomes equal to $$$\max(0, 3-3)=0$$$;  the $$$3$$$-rd monster attacks the $$$1$$$-st monster, after the attack the energy level of the $$$1$$$-st monster becomes equal to $$$\max(0, 2-0)=2$$$;  Nene uses the Attack Your Neighbour spell for the second time;  the $$$1$$$-st monster attacks the $$$2$$$-nd monster, after the attack the energy level of the $$$2$$$-nd monster becomes equal to $$$\max(0, 3-2)=1$$$;  the $$$2$$$-nd monster attacks the $$$3$$$-rd monster, after the attack the energy level of the $$$3$$$-rd monster becomes equal to $$$\max(0, 0-1)=0$$$;  the $$$3$$$-rd monster attacks the $$$1$$$-st monster, after the attack the energy level of the $$$1$$$-st monster becomes equal to $$$\max(0, 2-0)=2$$$;  Nene uses the Attack Your Neighbour spell for the third time;  the $$$1$$$-st monster attacks the $$$2$$$-nd monster, after the attack the energy level of the $$$2$$$-nd monster becomes equal to $$$\max(0, 1-2)=0$$$;  the $$$2$$$-nd monster attacks the $$$3$$$-rd monster, after the attack the energy level of the $$$3$$$-rd monster becomes equal to $$$\max(0, 0-0)=0$$$;  the $$$3$$$-rd monster attacks the $$$1$$$-st monster, after the attack the energy level of the $$$1$$$-st monster becomes equal to $$$\max(0, 2-0)=2$$$. After each of the next uses of the spell, energy levels of monsters do not change. Thus, only the $$$1$$$-st monster has a non-zero energy level in the end.In the second test case, both monsters initially have zero energy level.

Sample Inputs:
5
3
2 5 3
2
0 0
4
1 5 7 2
4
4 2 1 2
13
1 1 4 5 1 4 1 9 1 9 8 1 0

Sample Outputs:
1
1 
0

1
1 
2
1 3 
6
1 3 6 8 10 12

Solution (Python):
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
    sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
file = sys.stdin
if os.environ.get('USER') == 'loic':
    file = open('data.in')
line = lambda : file.readline().split()
ui = lambda : int(line()[0])
mi = lambda : map(int, line())
li = lambda : list(mi())
lsi = lambda : list(map(int, line()[0]))

def solve():
    arr = A.copy()
    stop = False
    while not stop:
        for i in range(1, N + 1):
            arr[i % N] = max(arr[i % N] - arr[i - 1], 0)
        c = 0
        stop = True
        for i in range(N + 4):
            if arr[i % N] != 0:
                c += 1
                if c > 3:
                    stop = False
                    break
            else:
                c = 0
    st = -1
    for i in range(1, N + 1):
        arr[i % N] = max(arr[i % N] - arr[i - 1], 0)
        if arr[i % N] == 0:
            st = i
            break
    c = 0
    for i in range(st, st + N + 1):
        if arr[i % N] == 0:
            if c == 2:
                arr[(i - 1) % N] = 0
            elif c == 3:
                d = arr[(i - 3) % N]
                k = arr[(i - 2) % N] // d
                rem = arr[(i - 2) % N] % d
                s = rem * k + d * (k - 1) * k // 2
                if arr[(i - 1) % N] <= s:
                    arr[(i - 1) % N] = 0
                arr[(i - 2) % N] = 0
            c = 0
        else:
            c += 1
    res = [i for i in range(N) if arr[i] != 0]
    return str(len(res)) + '\n' + ' '.join((str(v + 1) for v in res))
for test in range(1, ui() + 1):
    N = ui()
    A = li()
    print(solve())
file.close()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sint = lambda : int(input())
mint = lambda : map(int, input().split())
ints = lambda : list(map(int, input().split()))

def solve() -> None:
    n = sint()
    nums = ints()
    if n == 2:
        while nums[0] and nums[1]:
            nums[1] = max(0, nums[1] - nums[0])
            nums[0] = max(0, nums[0] - nums[1])
    elif n == 3:
        while nums[0] and nums[1] and nums[2]:
            nums[1] = max(0, nums[1] - nums[0])
            nums[2] = max(0, nums[2] - nums[1])
            nums[0] = max(0, nums[0] - nums[2])
        for i in range(n):
            if nums[i]:
                nums[(i + 1) % n] = 0
    else:

        def check() -> bool:
            for i in range(n):
                if nums[i] and nums[(i + 1) % n] and nums[(i + 2) % n] and nums[(i + 3) % n]:
                    return True
            return False
        while check():
            for i in range(n):
                nums[(i + 1) % n] = max(0, nums[(i + 1) % n] - nums[i])

        def cal(a: int, b: int) -> int:
            k = b // a
            return (b * 2 - (k + 1) * a) * k // 2
        for i in range(n):
            if not nums[i] and nums[(i + 1) % n]:
                d = cal(nums[(i + 1) % n], nums[(i + 2) % n])
                if i == n - 2:
                    d += nums[0]
                nums[(i + 3) % n] = max(0, nums[(i + 3) % n] - d)
                nums[(i + 2) % n] = 0
    ans = [i + 1 for (i, x) in enumerate(nums) if x]
    print(len(ans))
    print(*ans)
for _ in range(int(input())):
    solve()

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    while True:
        zero = None
        for i in range(1, n + 1):
            a[i % n] -= a[i - 1]
            if a[i % n] <= 0:
                a[i % n] = 0
                zero = i
        if zero == None:
            continue
        cont = 0
        ok = True
        for i in range(n):
            if a[(zero + i) % n] != 0:
                cont += 1
                if cont >= 4:
                    ok = False
                    break
            else:
                cont = 0
        if ok:
            break
    if a[0] > 0:
        a[1] = max(0, a[1] - a[0])
        if a[1] > 0 and len(a) > 2:
            a[2] = max(0, a[2] - a[1])
    i = 0
    while i < n:
        if a[(zero + i) % n] == 0:
            i += 1
        elif a[(zero + 1 + i) % n] == 0:
            i += 2
        elif a[(zero + 2 + i) % n] == 0:
            a[(zero + 1 + i) % n] = 0
            i += 3
        else:
            y = a[(zero + 1 + i) % n]
            x = a[(zero + i) % n]
            k = y // x
            a[(zero + 1 + i) % n] = 0
            a[(zero + 2 + i) % n] += k * (k + 1) * x // 2 - k * y
            i += 4
    ans = [i + 1 for i in range(n) if a[i] > 0]
    print(len(ans))
    print(*ans)