from collections import deque
def count(s):
n=len(s)
def flip_prefix(s,x):
return ''.join('1' if c=='0' else '0' for c in s[:x]) + s[x:]
visited=set()
q=deque()
visited.add(s)
q.append(s)
balance=0
valid_prefixes=[]
for i in range(n):
if s[i]=='1':
balance+=1
else:
balance-=1
if balance==0:
valid_prefixes.append(i+1)
while q:
cur=q.popleft()
for x in valid_prefixes:
next_s=flip_prefix(cur,x)
if next_s not in visited:
visited.add(next_s)
q.append(next_s)
return len(visited)
def main():
t=int(input())
for i in range(t):
n=int(input())
s=input()
print(count(s))
main()
Subtask Info
Time Limit Exceeded
Submission ID: 1150938820
Time:4.99s
Memory:20.3M
| Sub-Task | Task # | Result (time) |
|---|---|---|
| 1 | 0 | Correct (0.02) |
| 1 | 1 | Correct (0.02) |
| 1 | 2 | Correct (0.02) |
| 1 | 3 | Correct (1.51) |
| 1 | 4 | Time Limit Exceeded (4.99) |
| 1 | 5 | Skipped Testfile |
| Subtask Score: 0% | Result - Time Limit Exceeded | |
| Total Score = 0% |
||