Problem B has weak test cases. ↵
↵
<spoiler summary="Spoiler">↵
~~~~~↵
def check(arr,brr,mid,d):↵
count = 0 ↵
count2 = 0↵
for i in range(mid): ↵
count += d[arr[i]]*(mid- i) ↵
count2 += d[arr[i]] ↵
prev = 0 ↵
count3 = 0↵
j = mid -1↵
for i in range(len(brr)-1,-1,-1):↵
if brr[i] >= count2:↵
count3 += count2 ↵
count2 -= d[arr[j]]↵
count2 = max(0,count2)↵
j -= 1 ↵
j = max(0,j)↵
else:↵
count3 += brr[i] ↵
↵
↵
↵
if count3 >= count :↵
return True ↵
else:↵
return False ↵
↵
with open("input.txt", "r") as f_in, open("output.txt", "w") as f_out:↵
data = f_in.read().splitlines()↵
idx = 0↵
t = int(data[idx]); idx += 1↵
for _ in range(t):↵
n,m = map(int, data[idx].split()); idx += 1↵
arr = list(map(int, data[idx].split())) ; idx += 1 ↵
brr = list(map(int, data[idx].split())) ; idx += 1↵
brr.sort() ↵
arr.sort()↵
d = {} ↵
for i in arr:↵
if i in d:↵
d[i] += 1 ↵
else:↵
d[i] = 1 ↵
arr = set(arr) ↵
arr = list(arr) ↵
arr.sort()↵
arr = arr[::-1] ↵
l = 0↵
r = min(len(arr),len(brr)) ↵
while l < r :↵
mid = (l+r+1)//2 ↵
if check(arr,brr,mid,d):↵
l = mid ↵
else:↵
r = mid - 1↵
ans = 0 ↵
for i in range(l):↵
ans += d[arr[i]]↵
print(f"Case #{_+1}: {ans}", file = f_out)↵
↵
↵
↵
↵
↵
↵
~~~~~↵
</spoiler>↵
↵
My code got ac verdict but fails on test case ↵
↵
~~~~~↵
1↵
6 6↵
1 2 3 4 5 6 ↵
5 5 5 5 1 1↵
~~~~~↵
↵
↵
Output should be 5 but it gives 6. ↵
↵
PS-From around ranks 1200 to 2100, people solved only problems A and B most of them have wrong sol for B.
↵
<spoiler summary="Spoiler">↵
~~~~~↵
def check(arr,brr,mid,d):↵
count = 0 ↵
count2 = 0↵
for i in range(mid): ↵
count += d[arr[i]]*(mid- i) ↵
count2 += d[arr[i]] ↵
prev = 0 ↵
count3 = 0↵
j = mid -1↵
for i in range(len(brr)-1,-1,-1):↵
if brr[i] >= count2:↵
count3 += count2 ↵
count2 -= d[arr[j]]↵
count2 = max(0,count2)↵
j -= 1 ↵
j = max(0,j)↵
else:↵
count3 += brr[i] ↵
↵
↵
↵
if count3 >= count :↵
return True ↵
else:↵
return False ↵
↵
with open("input.txt", "r") as f_in, open("output.txt", "w") as f_out:↵
data = f_in.read().splitlines()↵
idx = 0↵
t = int(data[idx]); idx += 1↵
for _ in range(t):↵
n,m = map(int, data[idx].split()); idx += 1↵
arr = list(map(int, data[idx].split())) ; idx += 1 ↵
brr = list(map(int, data[idx].split())) ; idx += 1↵
brr.sort() ↵
arr.sort()↵
d = {} ↵
for i in arr:↵
if i in d:↵
d[i] += 1 ↵
else:↵
d[i] = 1 ↵
arr = set(arr) ↵
arr = list(arr) ↵
arr.sort()↵
arr = arr[::-1] ↵
l = 0↵
r = min(len(arr),len(brr)) ↵
while l < r :↵
mid = (l+r+1)//2 ↵
if check(arr,brr,mid,d):↵
l = mid ↵
else:↵
r = mid - 1↵
ans = 0 ↵
for i in range(l):↵
ans += d[arr[i]]↵
print(f"Case #{_+1}: {ans}", file = f_out)↵
↵
↵
↵
↵
↵
↵
~~~~~↵
</spoiler>↵
↵
My code got ac verdict but fails on test case ↵
↵
~~~~~↵
1↵
6 6↵
1 2 3 4 5 6 ↵
5 5 5 5 1 1↵
~~~~~↵
↵
↵
Output should be 5 but it gives 6. ↵
↵
PS-From around ranks 1200 to 2100, people solved only problems A and B most of them have wrong sol for B.
