1362E - Johnny and Grandmaster - CodeForces Solution


data structures greedy implementation math number theory sortings two pointers *1900

Please click on ads to support us..

Python Code:

import sys
from heapq import *

input = lambda: sys.stdin.buffer.readline().decode().rstrip()



mod = 10**9 + 7

def solve():
    n ,p = list(map(int,input().split()))
    arr = list(map(int,input().split()))
    if p == 1 : 
        print(n%2) 
        return
    ans = 0 
    h= [ -i for i in arr] 

    heapify(h) 
    cnt = {}
    nonzero = [] 
    
    while h : 
        ai = -heappop(h)
        try:
            cnt[ai] += 1 
        except :
            cnt[ai] = 1
        heappush(nonzero,-ai) 
        while nonzero and cnt[-nonzero[0]]%2 == 0 : 
            cnt[-nonzero[0]] = 0 
            heappop(nonzero) 
            
        if cnt[ai] : 
            if cnt[ai] == p : 
                cnt[ai] = 0 
                heappush(h,-(ai+1)) 
    f = False

    for i in sorted(cnt.keys(),reverse=1) :
        if cnt[i] :
            if f :
                ans -= cnt[i]*pow(p,i,mod)
            else:
                f = True
                ans += pow(p,i,mod)
            ans %= mod 
    print(ans)
 
for t in range(int(input())):
        solve()


Comments

Submit
0 Comments
More Questions

1245C - Constanze's Machine
1005A - Tanya and Stairways
1663F - In Every Generation
1108B - Divisors of Two Integers
1175A - From Hero to Zero
1141A - Game 23
1401B - Ternary Sequence
598A - Tricky Sum
519A - A and B and Chess
725B - Food on the Plane
154B - Colliders
127B - Canvas Frames
107B - Basketball Team
245A - System Administrator
698A - Vacations
1216B - Shooting
368B - Sereja and Suffixes
1665C - Tree Infection
1665D - GCD Guess
29A - Spit Problem
1097B - Petr and a Combination Lock
92A - Chips
1665B - Array Cloning Technique
1665A - GCD vs LCM
118D - Caesar's Legions
1598A - Computer Game
1605A - AM Deviation
1461A - String Generation
1585B - Array Eversion
1661C - Water the Trees