Problem:


Score : 400 points

Problem Statement

Snuke has decided to play a game using cards.
He has a deck consisting of N cards. On the i-th card from the top, an integer A_i is written.

He will perform the operation described below zero or more times, so that the values written on the remaining cards will be pairwise distinct. Find the maximum possible number of remaining cards. Here, N is odd, which guarantees that at least one card can be kept.

Operation: Take out three arbitrary cards from the deck. Among those three cards, eat two: one with the largest value, and another with the smallest value. Then, return the remaining one card to the deck.

Constraints

3 ≦ N ≦ 10^{5}

N is odd.

1 ≦ A_i ≦ 10^{5}

A_i is an integer.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 A_3 ... A_{N}

Output

Print the answer.

Sample Input 1

5
1 2 1 3 7

Sample Output 1

3

One optimal solution is to perform the operation once, taking out two cards with 1 and one card with 2. One card with 1 and another with 2 will be eaten, and the remaining card with 1 will be returned to deck. Then, the values written on the remaining cards in the deck will be pairwise distinct: 1, 3 and 7.

Sample Input 2

15
1 3 5 2 1 3 2 8 8 6 2 6 11 1 1

Sample Output 2

7



Sample input:
5
1 2 1 3 7


Sample output:
3

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
C = [0 for i in range(10**5+1)]
for a in A:
    C[a] += 1
s = False
for i in range(1, N+1):
    if C[i] >= 2:
        if C[i] % 2 == 0:
            s = not s
if s:
    print(len(set(A))-1)
else:
    print(len(set(A)))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
k = Counter(a)
b = list(k.values())
over_2 = [bb for bb in b if bb >= 2]
if sum(over_2) % 2 == 1:
    print(len(b))
else:
    if len(over_2) == 0:
        print(len(b))
    else:
        print(len(b) - 1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
k = Counter(a)
b = list(k.values())
over_2 = [bb for bb in b if bb >= 2]
if sum(over_2) % 2 == 1:
    print(len(b))
else:
    print(len(b) - 1)

Submission status: Wrong Answer

Solution code:
# ARC068D - Card Eater (ABC053D)
from collections import Counter


def main():
    N = int(input())
    A = tuple(map(int, input().split()))
    C = sorted(Counter(A).values(), reverse=1)
    ans, stock = 0, 0
    for i in C:
        if i == 1:
            ans += 1
        else:
            if i >= 3:
                ans += 1
                stock += i - 1
            else:
                if stock:
                    ans += 1
                    stock -= 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ARC068D - Card Eater (ABC053D)
from collections import Counter


def main():
    N = int(input())
    A = tuple(map(int, input().split()))
    C = sorted(Counter(A).values(), reverse=1)
    ans, stock = 0, 0
    for i in C:
        if i == 1:
            ans += 1
        else:
            if i >= 3:
                ans += 1
                stock += i - 1
            else:
                if stock:
                    ans += 1
                    stock -= 1
        print(i,ans,stock)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

di = {}
N = int(input())
As = list(map(int,input().split(" ")))

for a in As:
    if a not in di:
        di[a] = 1
    else:
        di[a] += 1
even = 0
odd = 0
for v in di.values():
    if v % 2 == 0:
        even += 1
    if v %2 == 1 and v != 1:
        odd += 1
em = even * 2
om = max(odd - even , 0) * 2

print(N - em - om)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
*A, = map(int, input().split())
cnt = Counter(A)
ans = N
duplicates = sorted([(a, d) for a, d in cnt.items() if d > 1], key=lambda x: x[0])
offset = 0
for _, d in duplicates:
    if offset: d -= offset; offset = 0;
    if d == 1: continue
    elif d % 2 == 0: ans -= d; offset = 1;
    else: ans -= d-1
ans -= offset
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
d={}
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1

t=[]
for i in d:
    t.append(d[i])
t.sort(reverse=True)
ans=len(t)
chk=0
#print(t)
for i in t:
    i-=1
    if chk==0:
        chk+=i
    elif chk>i:
        chk-=i
    else:
        chk=abs(chk-i)
print(max(1,ans-chk))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
d={}
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1

t=[]
for i in d:
    t.append(d[i])
t.sort(reverse=True)
ans=len(t)
chk=0
#print(t)
for i in t:
    i-=1
    if chk==0:
        chk+=i
    elif chk>i:
        chk-=i
    else:
        chk=abs(chk-i)
print(ans-chk)

Submission status: Wrong Answer

Solution code:
def calc(n):
  ret=n
  while ret>=3:
    ret=ret%3+ret//3
  return ret

n=int(input())
arr=list(map(int,input().split()))
cnt=[0]*(10**5+1)
for i in range(n):
  cnt[arr[i]]+=1
cnt1=0
cnt2=0
for i in range(n):
  tmp=calc(cnt[i])
  if tmp==1:
    cnt1+=1
  elif tmp==2:
    cnt2+=1
if cnt2%2==0:
  print(cnt1+cnt2)
else:
  print(cnt1+cnt2-1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N=int(input())
A=list(map(int,input().split()))
Ac=dict(Counter(A))
a=0
b=0
for i in Ac.keys():
    if Ac[i]>1:
        a+=Ac[i]-1
    else:
        b+=1
if a%2==0:
    print(N-a)
else:
    if b>0:
        print(N-a-1)
    else:
        print(N-a)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
print(min(len(set(a)), len(a)-2))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N=int(input())
A=[int(i) for i in input().split() ]
dd=defaultdict(int)
for a in A:
    dd[a]+=1
L=[]
for j in dd.values():
    L.append(j-1)
L=sorted(L,reverse=True)
s=0
t=0
for a in L:
    if s<=t:
        s+=a
    else:
        t+=a
k=len(L)-abs(s-t)
if k>0:
    print(k)
else:
    print(1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N=int(input())
A=[int(i) for i in input().split() ]
dd=defaultdict(int)
for a in A:
    dd[a]+=1
L=[]
for j in dd.values():
    L.append(j-1)
L=sorted(L,reverse=True)
s=0
t=0
for a in L:
    if s<=t:
        s+=a
    else:
        t+=a
print(len(L)-abs(s-t))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
sn=[0]*n
mi2=0
mi=0
for i in range(0,n):
    if sn[i]==1:
        mi2=1-mi2
    else:
        sn[i]=1
        mi+=1
print(mi-mi2)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
b=[a[0]]
k=1
c=0
for i in range(1,n):
 if i==k:
  if a[i]!=b[-1]:
   b.append(a[i])
   k=i+1
  else:
   k=i+2
   if i==n-1:
     c=1
print(len(b)-c)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
b=[a[0]]
k=1
for i in range(1,n):
 if i==k:
  if a[i]!=b[-1]:
   b.append(a[i])
   k=i+1
  else:
   k=i+2
print(len(b))

Submission status: Wrong Answer

Solution code:
n = input()
l = len(set([int(x) for x in input().split()]))
print(l - l % 2)

Submission status: Wrong Answer

Solution code:
l = int(input())
t = len(set(list(map(int, input().split()))))
print(t - (1 - (l & 1)))

Submission status: Wrong Answer

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

length = len(a)
cnt = 3
while True:
    t = a[cnt - 3:cnt]
    if t[0] == t[1]:
        del a[cnt - 1]
        del a[cnt - 3]
        cnt -= 1
    if cnt == len(a): break
    cnt += 1
print(len(a))

Submission status: Wrong Answer

Solution code:
from collections import Counter

input()
c = Counter(map(int, input().split()))
print(len(c))

Submission status: Wrong Answer

Solution code:
from collections import Counter
import heapq

n = int(input())
a = Counter(map(int, input().split()))

x = []
for k in a:
    if a[k] > 1:
        x.append(-(a[k] - 1))

heapq.heapify(x)

while len(x) > 1:
    u = abs(heapq.heappop(x))
    v = abs(heapq.heappop(x))
    n -= min(v, u) * 2
    d = abs(u - v)
    if d > 0:
        heapq.heappush(x, -d)

if len(x) > 0:
    n -= abs(heapq.heappop(x)) * 2

print(n)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import heapq

n = int(input())
a = Counter(map(int, input().split()))

x = []
for k in a:
    if a[k] > 1:
        x.append(-(a[k] - 1))

heapq.heapify(x)

while len(x) > 1:
    u = abs(heapq.heappop(x))
    v = abs(heapq.heappop(x))
    n -= v * 2
    d = abs(u - v)
    if d > 0:
        heapq.heappush(x, -d)

if len(x) > 0:
    n -= abs(heapq.heappop(x)) * 2

print(n)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import heapq

n = int(input())
a = Counter(map(int, input().split()))

x = []
for k in a:
    if a[k] > 1:
        x.append(-(a[k] - 1))

heapq.heapify(x)

while len(x) > 1:
    u = - heapq.heappop(x)
    v = - heapq.heappop(x)
    n -= v * 2
    d = u - v
    if d > 0:
        heapq.heappush(x, -d)

if len(x) > 0:
    n -= heapq.heappop(x) * 2
    pass

print(n)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import heapq

n = int(input())
a = Counter(map(int, input().split()))

x = []
for k in a:
    if a[k] > 1:
        x.append(-(a[k] - 1))

heapq.heapify(x)

while len(x) > 1:
    u = - heapq.heappop(x)
    v = - heapq.heappop(x)
    n -= v * 2
    d = u - v
    if d > 0:
        heapq.heappush(x, -d)

if len(x) > 0:
    n += heapq.heappop(x) * 2
    pass

print(n)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import heapq

n = int(input())
a = Counter(map(int, input().split()))

x = []
for k in a:
    if a[k] > 1:
        x.append(-(a[k] - 1))

heapq.heapify(x)

while len(x) > 1:
    u = - heapq.heappop(x)
    v = - heapq.heappop(x)
    n -= v * 2
    heapq.heappush(x, -(u - v))

if len(x) > 0:
    n += heapq.heappop(x) * 2
    pass

print(n)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
c = 0
e = 0
i = 0
while True:
    c += 1
    cai = 1
    while i != n - 1 and a[i] == a[i + 1]:
        cai += 1
        print(i)
        if i != n - 1:
            i += 1
        else:
            break
    if cai % 2 == 0:
        e += 1
    if i != n - 1:
        i += 1
    else:
        break
ans = c - (e % 2)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
D = {}
for i in A:
    if i in D:
        D[i] += 1
    else:
        D[i] = 1
cnt = 0
for k in D.keys():
    if D[k] % 2:
        D[k] = 1
    else:
        D[k] = 2
        cnt += 1
print(N - cnt * 2)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[int(i) for i in input().split()]
if len(set(l))==n:
    print(n)
    exit()
print(1)

Submission status: Wrong Answer

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

# n=15
# a=[15,1,3,5,2,1,3,2,8,8,6,2,6,11,1,1]

l=[0 for i in range(10**5+1)]

for i in a:
	l[i]+=1

left = 1
right = 10**5
nn=0

while left<right:
	while l[left]<=1 and left<right:
		left+=1
	nn+=1
	l[left]-=1
	while l[right]<=1 and left<right:
		right-=1
	nn+=1
	l[right]-=1



print(n-nn)

Submission status: Wrong Answer

Solution code:
input()
a = [0] * (100000 + 1)

for i in map(int, input().split()):
    a[i] += 1
    if a[i] == 3:
        a[i] >>= 1

c = [0, a.count(1), a.count(2)]

ans = 0
ans += (c[2] >> 1) << 1
ans += c[1]
ans -= c[2] & 1

print(ans)

Submission status: Wrong Answer

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

# n=15
# a=[1, 3, 5, 2, 1, 3, 2, 8, 50000, 6, 50000, 6, 11, 1, 8]

l=[0 for i in range(10**5+1)]

for i in a:
	l[i]+=1

left = 1
right = 10**5
n=0

while left<right:
	while l[left]<=1 and left<right:
		left+=1
	n+=l[left]-1
	left+=1
	while l[right]<=1 and left<right:
		right-=1
	n+=l[right]-1
	right-=1
	if left == right:
		n+=2


print(n)

Submission status: Wrong Answer

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


l=[0 for i in range(10**5+1)]

for i in a:
	l[i]+=1

left = 1
right = 10**5
while left<right:
	while l[left]<=1 and left<right:
		left+=1
	l[left]-=1
	while l[right]<=1 and left<right:
		right-=1
	l[right]-=1

	if left == right:
		n-=2
	else:
		n-=2

print(n)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding:utf-8 -*-

import math


x = int(input())
tmp = int(math.ceil(x / 11.0 * 2.0))
if 11 * tmp - 6 >= x:
    print(tmp-1)
else:
    print(tmp)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n = II()
    s = set(LI())
    return len(s) | 1


print(main())

Submission status: Time Limit Exceeded

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

from collections import Counter
ac = Counter(A)

ans = 0
td = dict()
for k, v in ac.items():
    da = v // 3
    ma = v % 3
    t = da + ma
    while t >= 3:
        da = v // 3
        ma = v % 3
        t = da + ma
    
    td[k] = t

ans = 0
two = 0
for k, v in td.items():
    if v == 1:
        ans += 1
    else:
        two += 1

if two % 2 == 0:
    ans += two
else:
    two -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
def input():
    return sys.stdin.readline()[:-1]
  
n = int(input())
a = [int(i) for i in input().split()]

dic = collections.defaultdict(int)
for i in range(n):
    dic[a[i]] += 1

ls = collections.deque()
for i in dic.keys():
    if dic[i] > 1:
        ls.append(i)

ans = n

for i in range(n//2):
    if max(dic.values()) == 1:
        break
    if len(ls) == 1 and dic[ls[0]] == 2:
        ans -= 2
        dic[ls[0]] -= 1
        break
    else:
        if len(ls) == 1:
            dic[ls[0]] -= 2
        else:
            dic[ls[0]] -= 1
            dic[ls[-1]] -= 1
        ans -= 2

    if dic[ls[0]] <= 1:
        ls.popleft()
    if len(ls) > 1:
        if dic[ls[-1]] <= 1:
            ls.pop()

print(ans)

Submission status: Time Limit Exceeded

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

cnt = [[num, a.count(num)] for num in set(a)]
k = len(cnt)

if k%2 ==0:
  print(k-1)
else:
  print(k)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
from collections import Counter
c=Counter(a)
k1,v1=c.most_common(2)[0]
while v1>1:
    if v1>2:
        c[k1]-=2
    else:
        k2,v2=c.most_common(2)[1]
        if v2>0:
            c[k1]-=1
            c[k2]-=1
    k1,v1=c.most_common(2)[0]
cnt=0
for k in c.keys():
    if c[k]==1:
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

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

count = 0
A.sort()
for i in range(N):
    if A.count(A[i]) > 1:
        if A.index(A[i]) != i:
            count += 1

if count % 2 == 0:
    print(N - count)
else:
    print(N - (count + 1))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
li = []
f = 0
for i in a:
    if i not in li:
        li.append(i)
    else:
        f += 1
if f % 2:
	print(len(li) - 1)
else:
	print(len(li))

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
ar = list(map(int,input().split(" ")))
br = set(ar)
count = 0
for r in br:
    count += ar.count(r) - 1
if count % 2 == 0:
    print(a - count)
else:
    print(a - count - 1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
c = 0
e = 0
i = 0
while i < len(a):
    c += 1
    ca = a.count(a[i])
    if ca % 2 == 0:
        e += 1
    i += ca
ans = c - (e % 2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
done = []
e = 0
for ai in a:
    if ai not in done:
        if a.count(ai) % 2 == 0:
            e += 1
        done.append(ai)
ans = len(done) - (e % 2)
print(ans)

Submission status: Accepted

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

ans = 0
eve = 0
for i in cntA.items():
    if i[1] % 2 == 0:
        eve += 1
    ans += 1
if eve % 2 == 0:
    print(ans)
else:
    print(ans-1)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
A = inpl()

c = Counter(A)

odd_cnt = 0
even_cnt = 0
for v in c.values():
    if v % 2 == 1:
        odd_cnt += 1
    else:
        even_cnt += 1
ans = 0
ans += odd_cnt
if even_cnt % 2 == 1:
    ans += even_cnt - 1
else:
    ans += even_cnt
print(ans)

Submission status: Accepted

Solution code:

from collections import Counter
def resolve():
    N = int(input())
    A = list(map(int, input().split()))

    CNT = Counter(A)

    q = 0
    for v in CNT.values():
        if v >= 2:
            q += v - 1

    ans = len(CNT.keys())
    if q % 2 == 0:
        print(ans)
    else:
        print(ans - 1)


if __name__ == "__main__":
    resolve()