USACO Swapity Swapity Swap

USACO 2020 February Contest, Silver¶

Problem 1. Swapity Swapity Swap¶

http://usaco.org/index.php?page=viewproblem2&cpid=1014

In [1]:

# SAMPLE INPUT
#7 2 2
#2 5
#3 7

In [2]:

from itertools import compress

fin = open("swap.in", "r")
fout = open("swap.out", "w")

N,M,K = map(int,fin.readline().split())
print("N M K",N,M,K)

swaps = []
for i in range(M):
    p,q = map(int,fin.readline().split())
    swaps.append((p,q))
    
print("swaps",swaps)

N M K 7 2 2
swaps [(2, 5), (3, 7)]

In [3]:

powersof2 = [2**x for x in range(30)]
print(powersof2)

[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912]

In [4]:

%%time

cows0 = [x for x in range(N+1)]
cows = cows0.copy()
pass1 = cows0.copy()

for p,q in swaps:
    # copy that 0th position! 
    pass1 = pass1[0:p]+pass1[q:p-1:-1]+pass1[q+1:] 

def makedouble(oldlist):
    newlist = cows0.copy()
    for dub in range(2):
        work = newlist.copy()
        for i in range(1,N+1):
            j = oldlist[i]
            newlist[i]=work[j]  
    return newlist

pass2 = makedouble(pass1)
pass4 = makedouble(pass2)
pass8 = makedouble(pass4)
pass16 = makedouble(pass8)
pass32 = makedouble(pass16)
pass64 = makedouble(pass32)
pass128 = makedouble(pass64)
pass256 = makedouble(pass128)
pass512 = makedouble(pass256)
pass1024 = makedouble(pass512)
pass2048 = makedouble(pass1024)
pass4096 = makedouble(pass2048)
pass8192 = makedouble(pass4096)
pass16384 = makedouble(pass8192)
pass32768 = makedouble(pass16384)
pass65536 = makedouble(pass32768)
pass131072 = makedouble(pass65536)
pass262144 = makedouble(pass131072)
pass524288 = makedouble(pass262144)
pass1048576 = makedouble(pass524288)
pass2097152 = makedouble(pass1048576)
pass4194304 = makedouble(pass2097152)
pass8388608 = makedouble(pass4194304)
pass16777216 = makedouble(pass8388608)
pass33554432 = makedouble(pass16777216)
pass67108864 = makedouble(pass33554432)
pass134217728 = makedouble(pass67108864)
pass268435456 = makedouble(pass134217728) 
pass536870912 = makedouble(pass268435456)

Wall time: 0 ns

In [5]:

dummyflags = []
dummystring = bin(K)
for c in range(2,len(dummystring)):
    dummyflags.append(int(dummystring[c]))

if len(dummyflags)<30:
    padding = [0]*(30-len(dummyflags))
else:
    padding = []
powerflags = dummyflags[::-1]+padding  
print(powerflags)

[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

In [6]:

allpass = [pass1,pass2,pass4,pass8,pass16,pass32,pass64,pass128,pass256,pass512,pass1024,
           pass2048,pass4096,pass8192,pass16384,pass32768,pass65536,pass131072,pass262144,
           pass524288,pass1048576,pass2097152,pass4194304,pass8388608,pass16777216,
           pass33554432, pass67108864, pass134217728, pass268435456, pass536870912]

needed = [need for need in compress(allpass,powerflags)]  
print(needed)

[[0, 1, 2, 4, 3, 5, 7, 6]]

In [7]:

for instructions in needed:
    work = cows.copy()
    for i in range(1,N+1):    
        j = instructions[i]
        cows[i]=work[j]

In [8]:

for i in range(1,len(cows)):
    print(cows[i],end=" ")
    fout.write(str(cows[i])+"\n")
fout.close()

1 2 4 3 5 7 6