Problem:

C: 一致

問題

長さ $N$ の数列 $a_i$ が与えられる。
次の条件を満たす整数 $K (1 \le K \le N)$ を全て出力せよ。

条件:
$a_1, \cdots, a_K$ をうまく並び替えると $a_{N-K+1}, \cdots, a_N$ と一致する。

制約

$1 \le N \le 10^5$

$1 \le a_i \le 10^9$

入力は全て整数

入力:

$N$

$a_1 \cdots a_N$

出力:

条件を満たす $K$ を昇順に空白区切りで出力せよ。また末尾に改行を出力せよ。

サンプル

サンプル入力 1

8
5 2 4 9 4 9 2 5

サンプル出力 1

1 2 4 6 7 8

サンプル入力 2

3
5 7 5

サンプル出力 2

1 2 3

サンプル入力 3

9
118 118 97 116 97 97 114 110 101

サンプル出力 3

9



Sample input:
8
5 2 4 9 4 9 2 5


Sample output:
1 2 4 6 7 8

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
src = list(map(int,input().split()))

ctr1 = Counter()
ctr2 = Counter()

ans = []
for i in range(N):
    ctr1.update([src[i]])
    ctr2.update([src[-i-1]])
    if ctr1 == ctr2:
        ans.append(i+1)

print(*sorted(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
src = list(map(int,input().split()))

ctr1 = Counter()
ctr2 = Counter()

ans = []
for i in range(N):
    ctr1.update([src[i]])
    ctr2.update([src[-i-1]])
    if ctr1 == ctr2:
        ans.append(i+1)
        ctr1 = Counter()
        ctr2 = Counter()

print(*sorted(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
src = list(map(int,input().split()))

ctr1 = Counter()
ctr2 = Counter()

ans = []
for i in range(N):
    ctr1.update([src[i]])
    ctr2.update([src[-i-1]])
    if ctr1 == ctr2:
        ans.append(i+1)
        ctr1 = Counter()
        ctr2 = Counter()

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))

from collections import Counter
N = int(input())
src = list(map(int,input().split()))

ctr1 = Counter()
ctr2 = Counter()

ans = []
for i in range(N):
    ctr1[src[i]] += 1
    ctr2[src[-i-1]] += 1
    for k, v in ctr1.items():
        if ctr2[k] != v:
            break
    else:
        ans.append(i+1)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = ''
t1, t2 = [], []

for i in range(n):
    t1.append(a[i])
    t2.append(a[n-1-i])
    if sorted(t1) == sorted(t2):
        ans += str(i+1) + ' '
print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
ans = ''
t1, t2 = [], []

for i in range(n):
    t1.append(a[i])
    t2.append(a[n-1-i])
    if Counter(t1) == Counter(t2):
        ans += str(i+1) + ' '
print(ans[:-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from bisect import bisect_left, insort

N = int(input())
src = list(map(int,input().split()))
ans = []
A, B = [], []

for i in range(N):
    a, b = src[i], src[-i-1]
    addA = False
    addB = False

    if a != b:
        j = bisect_left(B, a)
        if j != len(B) and B[j] == a:
            del B[j]
        else:
            addA = True

        j = bisect_left(A, b)
        if j != len(A) and A[j] == b:
            del A[j]
        else:
            insort(B, b)

        if addA:
            insort(A, a)

    if len(A) == len(B) == 0:
        ans.append(i+1)

print(*ans)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = input().split()
# a = list(map(int, input().split()))
ans = ''
# t1, t2 = [], []
t1, t2 = Counter(), Counter()
for i in range(n):
    t1.update(a[i])
    t2.update(a[n-1-i])
    t3 = t1 & t2
    t1 -= t3
    t2 -= t3
    if t1 == t2:
        ans += str(i+1) + ' '
print(ans[:-1])

Submission status: Accepted

Solution code:
import sys,heapq
n=int(sys.stdin.readline())
a=[int(e) for e in sys.stdin.readline().split()]
r=[]
x=[]
y=[]
for i in range(1,n+1):
	heapq.heappush(x,a[i-1])
	heapq.heappush(y,a[n-i])
	while x and y and x[0]==y[0]:
		heapq.heappop(x)
		heapq.heappop(y)
	if not x and not y: r.append(i)
print(' '.join(str(e) for e in r))

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect
from fractions import gcd
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
A = LI()

A_sort = sorted(A)
A_num = [bisect.bisect_left(A_sort,a) for a in A]
ans = []
A_cnt = [0 for _ in range(N)]
cnt = 0

for i in range(N):
    bf1 = A_cnt[A_num[i]]
    bf2 = A_cnt[A_num[N-i-1]]
    A_cnt[A_num[i]] += 1
    A_cnt[A_num[N-i-1]] -= 1
    cnt += (abs(A_cnt[A_num[i]]) - abs(bf1))
    cnt += (abs(A_cnt[A_num[N-i-1]]) - abs(bf2))
    if cnt == 0:
        ans.append(i+1)

print (*ans)