Problem:


Score : 400 points

Problem Statement

We have N balls. The i-th ball has an integer A_i written on it.

For each k=1, 2, ..., N, solve the following problem and print the answer.  

Find the number of ways to choose two distinct balls (disregarding order) from the N-1 balls other than the k-th ball so that the integers written on them are equal.

Constraints

3 \leq N \leq 2 \times 10^5

1 \leq A_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

For each k=1,2,...,N, print a line containing the answer.

Sample Input 1

5
1 1 2 1 2

Sample Output 1

2
2
3
2
3

Consider the case k=1 for example. The numbers written on the remaining balls are 1,2,1,2.

From these balls, there are two ways to choose two distinct balls so that the integers written on them are equal.

Thus, the answer for k=1 is 2.

Sample Input 2

4
1 2 3 4

Sample Output 2

0
0
0
0

No two balls have equal numbers written on them.

Sample Input 3

5
3 3 3 3 3

Sample Output 3

6
6
6
6
6

Any two balls have equal numbers written on them.

Sample Input 4

8
1 2 1 4 2 1 4 1

Sample Output 4

5
7
5
7
7
5
7
5



Sample input:
5
1 1 2 1 2


Sample output:
2
2
3
2
3

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int,input().split()))
ans = 0
d = {}
if len(l) == len(set(l)):
  for i in range(len(l)):
    print(0)
else:
  for s in l:
    if s not in d:
      d[s] = 1
    else:
      d[s] += 1
  for i in range(n):
    ans = 0
    for j,k in d.items():
      if l[i] == j and k >= 2:
        ans += (k-1)*(k-2)//2
      else:
        ans += k*(k-1)//2
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
A = np.array(list(map(int, input().split(' '))))

A_unique = np.unique(A)
num_dict = {}
for a in A_unique:
  tmp = np.sum(A==a)
  num_dict[a] = (tmp*(tmp-1)/2, (tmp-1)*(tmp-2)/2)
total = sum([x[0] for x in num_dict.values()])

for k in range(n):
  print(int(total - num_dict[A[k]][0] + num_dict[A[k]][1]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))

for i in range(n):
    l = a[:i]+a[i+1:]
    pattern = 0
    for j in range(n):
        sum = l.count(j)
        pattern += sum*(sum-1)//2
    print(pattern)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
N=int(input())
A=list(map(int,input().split()))

l=[0]*(N+1)
cnt=0

for k in range(N):
	for i in A:
		l[i]+=1
	l[A[k]]-=1

	for j in l:
		cnt+=(j*(j-1))//2
	print(cnt)
	cnt=0
	l=[0]*(N+1)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections

n = int(input())
a = list(input().split())


def combinations_count(n, r):
    if n-r < 0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


for k in range(n):
    ans = 0
    count = collections.Counter(a)
    for c in count:
        kosu = count[c]
        if a[k] == c:
            kosu -= 1
        ans += combinations_count(kosu, 2)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import math

N = int(input())
A = list(map(int, input().split()))

c2 = math.factorial(2)

for k in range(1, N+1):
    a = A[:k-1] + A[k:]
    count = Counter(a)

    sum = 0
    for k, v in count.items():
        if v < 2:
            continue
        sum += math.factorial(v) // (math.factorial(v - 2) * c2)
    print(sum)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import Counter
from collections import defaultdict

n = int(sys.stdin.readline())
a = ''.join(sys.stdin.readline().split())
c = Counter(a)
comb_num = defaultdict(int)
subtracted_comb_num = defaultdict(int)

def combinations_count(n, r):
    if n-r < 0: return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for key in c.keys():
    comb_num[key] = combinations_count(int(c[key]), 2)
    subtracted_comb_num[key] = combinations_count(int(c[key])-1, 2)

total_comb_num = sum(comb_num.values())
for num in a:
    print(total_comb_num - comb_num[num] + subtracted_comb_num[num])

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
a = list(map(str,input().split()))
c = collections.Counter(a)

comon = c.most_common()
ans = 0
for i in comon:
  if i[1] != 1:
  	ans += (i[1]*(i[1]-1)//2)
  
for i in a:
  if (ans-int(a.count(i))) < 0:
    print(0)
  else:
    co = a.count(i)
    print(ans-(co*(co-1)//2)+((co-1)*(co-2)//2))

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
nums = list(map(int, input().split()))


def comb(n, r):
    try:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    except:
        return 0


for i in range(n):
    a_list = nums.copy()
    a_list.pop(i)
    cnt = 0
    for j in set(a_list):
        u_num = a_list.count(j)
        cnt += comb(u_num, 2)

    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input())
A = list(map(int,input().split()))

num = [0] * N

for i in range(N):
    num[A[i] - 1] = num[A[i] - 1] + 1

a = [0] * N
b = [0] * N

for i in range(N):
    if num[i] >= 3:
        a[i] = comb(num[i] - 1, 2)
        b[i] = comb(num[i] - 1, 1)
    if num[i] == 2:
        a[i] = 0
        b[i] = 1

for i in range(N):
    print(sum(a) + sum(b) - b[A[i] - 1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = sorted(set(A))
ans = 0
for i in range(len(B)):
    ans += A.count(B[i])*(A.count(B[i])-1)/2
    
for i in range(N):
         print(int(ans-A.count(A[i])*(A.count(A[i])-1)/2 +(A.count(A[i])-1)*(A.count(A[i])-2)/2))

Submission status: Time Limit Exceeded

Solution code:
import math

def combinations_count(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
a = [int(i) for i in input().split()]

for i in range(n):
    value = 0
    ra = a.copy()
    ra.pop(i)
    for j in set(ra):
        value += combinations_count(ra.count(j), 2)
    print(value)

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb
N,*A = map(int,open(0).read().split())
d = {}
for i in A:
    d[i]= d[i]+1 if i in d else 1
for i in A:
    dd = d.copy()
    dd[i] -= 1
    sum = 0
    for k,v in dd.items():
        sum += comb(v,2,exact=True)
    print(sum)

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np
import collections

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
  ans = 0
  b = copy.copy(a)
  b.pop(i)
  c = np.array(list(collections.Counter(b).values()))
  d = int(sum(c*(c-np.ones(len(c)))//2))
  print(d)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = input()
li = list(map(int,input().split()))
l_set = set(li)
ans_dic = {}
for i in l_set:
    temp = 0
    li2 = li[:]
    li2.remove(i)
    c = collections.Counter(li2)
    c_items = list(c.items())
    for j in c_items:
        temp += ((j[1] * (j[1]-1)) // 2)
    ans_dic[i] = temp
for k in li:
    print(ans_dic[k])

Submission status: Time Limit Exceeded

Solution code:
def func(num):
    return int(num * (num - 1) / 2)


n = int(input())
a = list(map(int, input().split()))
dict = {}
dict2 = {}
for i in range(n):
    if a[i] in dict:
        dict[a[i]] = dict[a[i]] + 1
    else:
        dict[a[i]] = 1
for i in range(n):
    # print("xxx", i, a[i])
    sum = 0
    if a[i] in dict2:
        print(dict2[a[i]])
    else:
        for key, value in dict.items():
            if key == a[i]:
                # print("aaa")
                sum = sum + func(value - 1)
            else:
                # print("bbb")
                sum = sum + func(value)
            # print("yyy", key, value, sum)
        print(sum)
        dict2[a[i]] = sum

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-

comb_dic = {}

def combination_formula_MOD(n, r, MOD):
    """nCrを O(min(n-r, r)) で高速に計算する"""
    def _inv(x, MOD):
        """xの逆元を返す"""
        return pow(x, MOD-2, MOD)
    if r > n: return 0

    if (n,r) in comb_dic:
        return comb_dic[(n,r)]

    r = min(n-r, r)
    bunsi, bunbo = 1, 1
    for i in range(r):
        bunsi = bunsi*(n-i)%MOD
        bunbo = bunbo*(i+1)%MOD

    ans = (bunsi*_inv(bunbo, MOD))%MOD
    comb_dic[(n,r)] = ans
    return ans


def combination_formula(n, r):
    """nCrは、O(min(n-r, r))で実装する
    Notes:
        分子と分母がかなり大きな値になった場合、計算は遅くなるので注意
        求める値がmodをとった値でいい場合、フェルマーの小定理を使った方法が速い。
    """
    if r > n: return 0

    if (n,r) in comb_dic:
        return comb_dic[(n,r)]

    r = min(n-r, r)
    bunsi, bunbo = 1, 1
    for i in range(r):
        bunsi = bunsi*(n-i)
        bunbo = bunbo*(i+1)

    comb_dic[(n,r)] = bunsi//bunbo
    return bunsi//bunbo


def solve():
    N = int(input())
    As = list(map(int, input().split()))
    MOD = 10**9+1

    dic = {}
    for a in As:
        if not a in dic:
            dic[a] = 0
        dic[a] += 1

    calc_dic = {}  # すでに計算済みのもの
    for a in As:
        ans = 0
        if not a in calc_dic:
            for key, value in dic.items():
                if key == a:
                    value -= 1
                ans += combination_formula(value, 2)
            calc_dic[a] = ans
            print(calc_dic[a])
        else:
            print(calc_dic[a])



if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import copy

N = int(input())
li = list(map(int, input().split()))
set_li = set(li)
r = range(N)
for num in r:
    total = 0
    li2 = copy.copy(li)
    del li2[num]
    for n in set_li:
        c = li2.count(n)
        total += c*(c-1)/2
    print(int(total))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Ai = list(map(int,input().split()))
Aisort = sorted(Ai) + [-1]
Aidic = {}
cnt = 1
for i in range(1,N+1):
    if Aisort[i] != Aisort[i-1]:
        Aidic.update([(str(Aisort[i-1]), cnt)])
        cnt = 1
    else:
        cnt = cnt + 1

for A in Ai:
    cnt = 0
    for i, indx in enumerate(Aidic):
        num = int(Aidic[indx])
        if str(A) == indx:
            cnt = cnt + (num-1)*(num-2)//2
        else:
            cnt = cnt + num*(num-1)//2
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
import collections

N = int(input())
BALLS = list(map(int, input().split()))

COUNTS = collections.Counter(BALLS)


MEMO = {}
def fact(n):
    if MEMO.get(n):
        return MEMO[n]
    r = 2
    if n - r < 0:
        return 0
    MEMO[n] = factorial(n) // factorial(r) // factorial(n - r)
    return MEMO[n]

MEMO2 = {}
def solve(n):
    if MEMO2.get(n):
        return MEMO2[n]

    MEMO2[n] = sum(fact(v if k != n else v - 1) for (k, v) in COUNTS.items())
    return MEMO2[n]

for i in range(N):
    print(solve(BALLS[i]))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
li = list(map(int,input().split()))

for i in range(n):
    new_list = []
    Sum = 0
    if i == 0:
        new_list = li[1:n]
        S=Counter(new_list)
        for k in range(n):
            if S[k] > 1:
                Sum += (S[k] * (S[k] -1)) / 2
            else:
                continue
        print(int(Sum))
    elif i == n-1:
        new_list = li[:n-1]
        S=Counter(new_list)
        for k in range(n):
            if S[k] > 1:
                Sum += (S[k] * (S[k] -1)) / 2
            else:
                continue
        print(int(Sum))
    else:
        new_list = li[:i] + li[i+1:]
        S=Counter(new_list)
        for k in range(n):
            if S[k] > 1:
                Sum += (S[k] * (S[k] -1)) / 2
            else:
                continue
        print(int(Sum))

Submission status: Time Limit Exceeded

Solution code:
import copy
import itertools

N = int(input())
A = list(map(int,input().split()))

for i in range(N):
    tmp = copy.deepcopy(A)
    tmp.pop(i)

    res = 0
    for j in list(set(tmp)):
        l = tmp.count(j)
        if(l<2):
            continue
        else:
            res += len(list(itertools.combinations(list(range(l)),2)))

    print(res)

Submission status: Time Limit Exceeded

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

NMAX=2*10**5

tmp = [0]*(NMAX+1)
tmp2 = [0]*(NMAX+1)
for n in c:
    k= c[n]-1
    tmp[n] = (c[n] * (c[n] - 1) // 2)
    tmp2[n] = (k * (k - 1) // 2)

for a in A:
    sum = 0
    for i in c:
        if a ==i:
            sum += tmp2[i]
        else:
            sum += tmp[i]
    print(sum)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
d = {}

for i in range(n):
    if a[i] in d:
        d[a[i]] += 1
    else:
        d[a[i]] = 1

for i in range(n):
    b = a[i]
    d[b] = d[b]-1
    count = 0
    for j in d:
        temp_count = d[j]*(d[j]-1)//2
        count += temp_count
    d[b] = d[b] + 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools,sys,collections,math,random,fractions,bisect;sys.setrecursionlimit(10**7)
sr = sys.stdin.readline; P = print; P2 = lambda x: print(*x, sep="\n")
def I(i=0): t = [int(x)-i for x in sr().split()];return t
def S(): t = sr().split(); return t if len(t) > 1 else t[0]
L1,L2,L3,L4, = [],[],[],[]

N, = I()
A = I()
d = dict()
def dd(a,b):
    if (a,b) in d:
        return d((a,b))
    else:
        return len(list(itertools.combinations(range(a),b)))
c = collections.Counter(A) 
total = 0
for e in c.items():
    total += dd(e[1],2)
for e in A:
    print(total -  dd(c[e],2) + dd(c[e]-1,2))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)

ansers = dict()
for i in range(N):
    if A[i] in ansers:
        print(ansers[A[i]])
    else:
        temp = sum(v*(v-1)//2 if A[i]!=k else (v-1)*(v-2)//2 for k, v in C.items())
        print(temp)
        ansers[A[i]] = temp

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(k) for k in input().split(' ')]

from collections import Counter 
import math 

res = []

for k in range(1, N + 1):
  A_tmp = list(A) # list() to make a new copy and avoid editing the original list
  del A_tmp[k - 1]
  A_tmp = Counter(A_tmp)

  n = 0
  for i in range(len(A_tmp)):
    j = list(A_tmp.values())[i]
    if j >= 2:
      n += math.factorial(j) // math.factorial(2) // math.factorial(j - 2)
  res.append(n)



print('\n'.join([str(s) for s in res]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))

# print(n)
# print(a)
for i in range(n):
    com = 0
    a2 = a[:]
    del a2[i]
    a3 = list(set(a2))
    for j in range(len(a3)):
        cnt = a2.count(a3[j])
        if cnt > 1:
            com = com + ((cnt * (cnt - 1)) / 2)
    else:
        print(int(com))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	ap = {}
	for i in A:
		if i in ap:
			ap[i] += 1
		else:
			ap[i] = 1

	#print(ap)

	for i in A:
		ap_tmp = ap.copy()
		ap_tmp[i] -= 1
		#print(ap_tmp)
		ans = 0
		for k, v in ap_tmp.items():
			if v > 1:
				ans += cmb(v, 2)
		print(ans)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def int_sqrt2(n):
    def f(prev):
        while True:
            m = (prev + n / prev) / 2
            if m >= prev:
                return prev
            prev = m

    return f(int(math.sqrt(n) * (1 + 1e-10)))

# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import combinations
N = int(input())
items = list(map(int, input().split()))
counts = Counter(items)
cobinations = {}
count_sum = 0
for key,value in counts.items():
  if value not in cobinations:
    if value > 1:
      tmp_key = list(range(value))
      count = len(list(combinations(tmp_key, 2)))
      cobinations[value] = count
    else:
      cobinations[value] = 0
  count_sum+=cobinations[value]

for key in items:
  value = counts[key]
  if value - 1 not in cobinations:
    if value - 1 > 1:
      tmp_key = list(range(value-1))
      count = len(list(combinations(tmp_key, 2)))
      cobinations[value-1] = count
    else:
      cobinations[value-1] = 0
  
  before = cobinations[value]
  after = cobinations[value-1]
  print(count_sum - before + after)

Submission status: Time Limit Exceeded

Solution code:
import copy
import collections
n=int(input())
retsu=input().split()
for i in range(len(retsu)) :
  count=0
  current=copy.deepcopy(retsu)
  current.pop(i)
  item=collections.Counter(current).values()
  
  for youso in item :
  	count+=int(youso*(youso-1)/2)
  print(count)

Submission status: Time Limit Exceeded

Solution code:
n = input()
n = int(n)
a = input().split(" ")
a = [int(i) for i in a]

c = [a.count(i+1) for i in range(n)]

r = []

for i in range(n):
  if c[i] == 0:
    r.append(0)
  else:
    ctmp = [j for j in c]
    ctmp[i] = c[i] - 1
    tmp = 0
    for j in range(n):
      tmp = tmp + int(ctmp[j] * (ctmp[j] - 1) / 2)
    r.append(tmp)

for i in range(n):
  print(r[a[i]-1])

Submission status: Time Limit Exceeded

Solution code:
import math
def fcomb(a, b):
  if a <= 1:
    return 1
  return math.factorial(a) // math.factorial(a - b) // math.factorial(b)

N = int(input())
nMax = 2 * 10 ** 5
l = [0] * (nMax + 1)
ak = list(map(int, input().split()))
numMax = 0
for num in ak:
  l[num] += 1
  if num > numMax:
    numMax = num
for i in range(N):
  l[ak[i]] -= 1
  total = 0
  for j in range(numMax + 1):
    if l[j] >= 2:
      total += fcomb(l[j], 2)
  l[ak[i]] += 1
  print(total)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
A_list = [int(_) for _ in input().split()]

for k in range(N):
    ans = 0
    test = A_list[:k] + A_list[(k+1):]
    temp = Counter(test)
    for k, v in temp.items():
        if v < 2:
            continue
        ans += v*(v-1)/2
    print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
# import numpy as np
from functools import reduce
# import statistics
import decimal
import heapq
import collections
import itertools

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

n = int(input())
d = getInputListInt()


def combinations_count(n, r):
    if n <= 1:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

dic = {}
dic_ans = {}

for key in d:
    if key in dic:
        dic[key] += 1
    else:
        dic[key] = 1

for i in range(n):
    ans=0
    tmp_key = d[i]

    if tmp_key in dic_ans:
        print(dic_ans[tmp_key])
    else:
        for k in dic:
            if k == tmp_key:
                ans += combinations_count(dic[k]-1, 2)
            else:
                ans += combinations_count(dic[k], 2)
        print(ans)
        dic_ans[tmp_key] = ans

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = input().split()
arr = [int(i) for i in arr]
dic = {}
for i in arr:
    if i in dic.keys():
        dic[i] += 1
    else:
        dic[i] = 1

dic2 = {}
for i in dic:
    sum = 0
    if dic[i] > 2:
        sum = (dic[i] - 1) * (dic[i] - 2) // 2
    for j in dic:
        if i != j and dic[j] > 1:
            sum += dic[j] * (dic[j] - 1) // 2
    dic2[i] = sum
for i in arr:
    print(dic2[i])

Submission status: Time Limit Exceeded

Solution code:
def c2(x):
    return x * (x - 1) // 2


n = int(input())
a = list(map(int, input().split()))
b = list(a.count(i) for i in range(1, n + 1))
c = list(c2(b[i]) for i in range(n))
d = list(c2(b[i] - 1) for i in range(n))

for k in range(n):
    i = a[k]
    ans = sum(c) - c[i - 1] + d[i - 1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
balls = list(map(int, input().split(' ')))

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
 
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
 
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
 
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
 
    return result

for i in range(N):
  sum_result = 0
  balls_all = balls[0:i] + balls[i+1:]
  balls_uni = set(balls_all)

  for j, ball in enumerate(balls_uni):
    a = balls_all.count(ball)
    if a >= 2:
      sum_result += cmb(a, 2)
  print(sum_result)

Submission status: Time Limit Exceeded

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input().rstrip())
As = [int(x) for x in input().rstrip().split()]
d = {}
for n in As:
    if n not in d.keys():
        d[n] = 1
    else:
        d[n] += 1
ans = {}
for n in As:
    if n in ans.keys():
        print(ans[n])
        continue
    d[n] -= 1
    ret = 0
    for val in d.values():
        if val > 1:
            ret += combinations_count(val, 2)
    ans[n] = ret
    print(ret)
    d[n] += 1

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
A_array = list(map(int, input().split()))
Ai_dict = Counter(A_array)


def calc_comb(Ai_dict):
    num = 0
    for k,v in Ai_dict.items():
        num += v*(v-1)/2
    return int(num)


res_dict = dict([])

for n in A_array:
    if not n in res_dict.keys():
        res_dict[n] = calc_comb(Ai_dict) - Ai_dict[n]+1
    print(res_dict[n])

Submission status: Time Limit Exceeded

Solution code:
import collections as cc
n=int(input())
l=list(map(int,input().split()))
ff=cc.Counter(l)
ff=dict(ff)
ans=[]
for i in range(n):
    f=ff.copy()
    f[l[i]]=max(0,f[l[i]]-1)
    t=0
    for i in f:
        x=f[i]
        t+=(x*(x-1))//2
    ans.append(t)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))

p = 7+pow(10,9)
def cmb(n,r,p):
    numerator = 1
    for i in range(n-r+1, n+1):
        numerator = numerator * i % p
    denominator = 1
    for i in range(1, r+1):
        denominator = denominator * i % p
    return numerator * pow(denominator, p-2, p) % p

b = list(set(a))

n_b = len(b)
c = []

for i in range(n_b):
    c.append(a.count(b[i]))

d = []

for i in range(n_b):
    if c[i] == 1:
        continue
    else:
        d.append(cmb(c[i], 2, p))

d = sum(d)


for i in range(n):
    if a.count(a[i]) == 1:
        print(d)
    elif a.count(a[i]) == 2:
        print(d-1)
    else:
        print(d - cmb(a.count(a[i]), 2, p) + cmb(a.count(a[i])-1, 2, p))

Submission status: Time Limit Exceeded

Solution code:

N=int(input())
A=list(map(int,input().split()))
B=list(set(A))
C=[]
D=[]
for i in B:
    k=A.count(i)


    C.append(int((k-1)*(k-2)/2))
    D.append(int(k*(k-1)/2))
Dsum=sum(D)
for i in A:

    iindex=B.index(i)
    iindexnum=C[iindex]
    num=Dsum-D[iindex]
    ans=iindexnum+num
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def combinations_count(n, r):
    if n - r < 0:
        return 0
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))


N = INT()
A = LIST()

ans = 0

C = Counter(A)
for i in list(C.values()):
    ans += combinations_count(i, 2)

for i in range(N):
    tmp = ans - combinations_count(C[A[i]], 2) + combinations_count(C[A[i]] - 1, 2)
    print(tmp)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict
def per_count(n, r):
    result = 0
    if n >= r:
        result = (math.factorial(n) // math.factorial(n - r)) // 2
    return result
N = int(input())
A = [int(a) for a in input().split()]
d = defaultdict(int)
max = 0
for a in A:
    d[a] += 1
    if max < d[a]:
        max = d[a]
Z = [per_count(i, 2) for i in range(max+1)]
for a in A:
    d[a] -= 1
    result = 0
    for k in d.keys():
        result += Z[d[k]]
    print(result)
    d[a] += 1

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
balls = input()
balls = balls.split()
balls = list(map(int, balls))

count = defaultdict(int)
for i in balls:
  count[i] += 1

def cmb(M):
  return M*(M-1)//2

sum = defaultdict(int)
for i in count:
  for j in count:
    if i==j:
      sum[i] += cmb(count[j]-1)
    else:
      sum[i] += cmb(count[j])
      
for i in balls:
  print(sum[i])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
D={}
x=0
for a in A:
	if a in D.keys():
		D[a]=D[a]+1
	else:
		D[a]=1

for i in range(len(A)):
	if D[A[i]]>1:
		D[A[i]]=D[A[i]]-1
	else:
		D.pop(A[i])
	x=0
	lis=list(D.keys())
	for j in range(len(D.keys())):
		y=D[lis[j]]
		x+=int((y**2-y)/2)
	print(x)
	if A[i] in D.keys():
		D[A[i]]=D[A[i]]+1
	else:
		D[A[i]]=1

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))

dict_A={}
B=list(set(A))
C=0

for a in A:
    if a not in dict_A.keys():
        dict_A[a]=1
    else:
        dict_A[a]+=1

for n in range(N):
    C=0
    for i in dict_A.keys():
        if A[n]==i:
            C+=(dict_A[i]-1)*(dict_A[i]-2)//2
        else:
            C+=dict_A[i]*(dict_A[i]-1)//2
    print(C)
#print(dict_A)
#print(B)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A_set = list(set(A))
Ad = {a_set: A.count(a_set) for a_set in A_set}
Ad_score = {}
for ad_key, ad_value in Ad.items():
  Ad_ = Ad.copy()
  Ad_[ad_key] -= 1
  Ad_score[ad_key] = sum([(x>1) * x * (x-1) / 2 for x in list(Ad_.values())])

A_out = [str(int(Ad_score[a])) for a in A]
print('\n'.join(A_out))