Problem p02618 (python)

Fixed submission:
d = int(input())
clist = list(map(int,input().split()))
last_c = [0]*26

slist = [0] * d
for i in range(d):
    slist[i] = list(map(int,input().split()))

tlist = [0]*d

satisfy = [0]*(d+1)

for i in range(0,d):
    max = 0
    max_n = 0
    for n in range(26):
        if i > 0:
            curr = slist[i][n] + satisfy[i-1]
        else:
            curr = slist[i][n]
        minus = 0
        for j in range(26):
            if n != j:
                minus -= clist[j] * (i - last_c[j])
        curr += minus
        if curr > max:
            max = curr
            max_n = n
    satisfy[i] = max
    last_c[max_n] = i+1 
    tlist[i] = max_n+1

#remove first
for i in tlist:
    print(i)

Buggy submission (verdict: Runtime Error):

import time
st = time.time()

d = int(input())
clist = list(map(int,input().split()))
last_c = [0]*26
select_c = [0]*26
for i in range(26):
    select_c[i] = []

slist = [0] * d
for i in range(d):
    slist[i] = list(map(int,input().split()))

tlist = [0]*d
satisfy = [0]*(d+1)

#貪欲法
for i in range(0,d):
    max = 0
    max_n = 0
    for n in range(26):
        if i > 0:
            curr = slist[i][n] + satisfy[i-1]
        else:
            curr = slist[i][n]
        minus = 0
        for j in range(26):
            if n != j:
                minus -= clist[j] * (i - last_c[j])
        curr += minus
        if curr > max:
            max = curr
            max_n = n
    satisfy[i] = max
    last_c[max_n] = i+1 
    select_c[max_n].append(i+1)
    tlist[i] = max_n+1

import random
import numpy as np

sum = 0
total_c = 0


for i in range(d):
    sum += slist[i][tlist[i]-1]

ct = time.time()

for i in range(len(select_c)):
    start = 1
    c_change = 0
    if select_c[i] == []:
        c_change = np.sum(np.arange(d+1))
    else:
        for j in range(len(select_c[i])):
            end = select_c[i][j]
            if end > start:
                c_change += np.sum(np.arange(end-start+1))
            start = end
        end = d+1
        c_change += np.sum(np.arange(end-start))
        start = end
    total_c += clist[i]*c_change

current_max = sum - total_c

import bisect
while ct-st < 1.9:
    change_d = random.randint(1,d)
    change_d_to_c = random.randint(0,len(select_c)-1)
    for x in range(len(select_c)):
        try:
            ind = select_c[x].index(change_d)
            change = x
            s_change = slist[change_d-1][ind]
            select_c[x].remove(change_d)
            break
        except:
            None

    s_change2 = slist[change_d-1][change_d_to_c]

    bisect.insort(select_c[change_d_to_c],change_d)
    #calc
    sum2 = sum - s_change + s_change2
    total_c2 = 0
    for i in range(len(select_c)):
        start = 1
        c_change = 0
        if select_c[i] == []:
            c_change = np.sum(np.arange(d+1))
        else:
            for j in range(len(select_c[i])):
                end = select_c[i][j]
                if end > start:
                    c_change += np.sum(np.arange(end-start+1))
                start = end
            end = d+1
            c_change += np.sum(np.arange(end-start))
            start = end
        total_c2 += clist[i]*c_change

    if sum - total_c < sum2 - total_c2:
        sum = sum2
        total_c = total_c2
        tlist[change_d-1] = change_d_to_c+1
    else:
        bisect.insort(select_c[change],change_d)
        select_c[change_d_to_c].remove(change_d)

    ct = time.time()
    
#remove first
for i in tlist:
    print(i)

Buggy submission (verdict: Runtime Error):

import time
st = time.time()

d = int(input())
clist = list(map(int,input().split()))
last_c = [0]*26
select_c = [0]*26
for i in range(26):
    select_c[i] = []

slist = [0] * d
for i in range(d):
    slist[i] = list(map(int,input().split()))

tlist = [0]*d
satisfy = [0]*(d+1)

#貪欲法
for i in range(0,d):
    max = 0
    max_n = 0
    for n in range(26):
        if i > 0:
            curr = slist[i][n] + satisfy[i-1]
        else:
            curr = slist[i][n]
        minus = 0
        for j in range(26):
            if n != j:
                minus -= clist[j] * (i - last_c[j])
        curr += minus
        if curr > max:
            max = curr
            max_n = n
    satisfy[i] = max
    last_c[max_n] = i+1 
    select_c[max_n].append(i+1)
    tlist[i] = max_n+1

import random
import numpy as np

sum = 0
total_c = 0


for i in range(d):
    sum += slist[i][tlist[i]-1]

ct = time.time()

for i in range(len(select_c)):
    start = 1
    c_change = 0
    if select_c[i] == []:
        c_change = np.sum(np.arange(d+1))
    else:
        for j in range(len(select_c[i])):
            end = select_c[i][j]
            c_change += np.sum(np.arange(end-start+1))
            start = end
        end = d+1
        c_change += np.sum(np.arange(end-start))
        start = end
    total_c += clist[i]*c_change

current_max = sum - total_c

import bisect
while ct-st < 1.9:
    change_d = random.randint(1,d)
    change_d_to_c = random.randint(0,len(select_c)-1)
    for x in range(len(select_c)):
        try:
            index = select_c[x].index(change_d)
            change = x
            s_change = slist[change_d-1][index]
            select_c[x].remove(change_d)
            break
        except:
            None

    s_change2 = slist[change_d-1][change_d_to_c]

    bisect.insort(select_c[change_d_to_c],change_d)
    #calc
    sum2 = sum - s_change + s_change2
    total_c2 = 0
    for i in range(len(select_c)):
        start = 1
        c_change = 0
        if select_c[i] == []:
            c_change = np.sum(np.arange(d+1))
        else:
            for j in range(len(select_c[i])):
                end = select_c[i][j]
                c_change += np.sum(np.arange(end-start+1))
                start = end
            end = d+1
            c_change += np.sum(np.arange(end-start))
            start = end
        total_c2 += clist[i]*c_change

    if sum - total_c < sum2 - total_c2:
        sum = sum2
        total_c = total_c2
        tlist[change_d-1] = change_d_to_c+1
    else:
        bisect.insort(select_c[change],change_d)
        select_c[change_d_to_c].remove(change_d)

    ct = time.time()
    
#remove first
for i in tlist:
    print(i)

Buggy submission (verdict: Runtime Error):

import time
st = time.time()

d = int(input())
clist = list(map(int,input().split()))
last_c = [0]*26
select_c = [0]*26
for i in range(26):
    select_c[i] = []

slist = [0] * d
for i in range(d):
    slist[i] = list(map(int,input().split()))

tlist = [0]*d
satisfy = [0]*(d+1)

#貪欲法
for i in range(0,d):
    max = 0
    max_n = 0
    for n in range(26):
        if i > 0:
            curr = slist[i][n] + satisfy[i-1]
        else:
            curr = slist[i][n]
        minus = 0
        for j in range(26):
            if n != j:
                minus -= clist[j] * (i - last_c[j])
        curr += minus
        if curr > max:
            max = curr
            max_n = n
    satisfy[i] = max
    last_c[max_n] = i+1 
    select_c[max_n].append(i+1)
    tlist[i] = max_n+1

import random
import numpy as np

sum = 0
total_c = 0


for i in range(d):
    sum += slist[i][tlist[i]-1]

ct = time.time()

for i in range(len(select_c)):
    start = 1
    c_change = 0
    if select_c[i] == []:
        c_change = np.sum(np.arange(d+1))
    else:
        for j in range(len(select_c[i])):
            end = select_c[i][j]
            c_change += np.sum(np.arange(end-start+1))
            start = end
        end = d+1
        c_change += np.sum(np.arange(end-start))
        start = end
    total_c += clist[i]*c_change

current_max = sum - total_c

import bisect
while ct-st < 1.9:
    change_d = random.randint(1,d)
    change_d_to_c = random.randint(0,len(select_c)-1)
    for x in range(len(select_c)):
        try:
            index = select_c[x].index(change_d)
            change = x
            s_change = slist[change_d-1][index]
            select_c[x].remove(change_d)
            break
        except:
            None

    s_change2 = slist[change_d-1][change_d_to_c]

    bisect.insort(select_c[change_d_to_c],change_d)
    #calc
    sum2 = sum - s_change + s_change2
    total_c2 = 0
    for i in range(len(select_c)):
        start = 1
        c_change = 0
        if select_c[i] == []:
            c_change = np.sum(np.arange(d+1))
        else:
            for j in range(len(select_c[i])):
                end = select_c[i][j]
                c_change += np.sum(np.arange(end-start+1))
                start = end
            end = d+1
            c_change += np.sum(np.arange(end-start))
            start = end
        total_c2 += clist[i]*c_change

    if sum - total_c < sum2 - total_c2:
        sum = sum2
        total_c = total_c2
        tlist[change_d-1] = change_d_to_c+1
    else:
        bisect.insort(select_c[change],change_d)
        select_c[change_d_to_c].remove(change_d)

    ct = time.time()
    
#remove first
for i in tlist:
    if i < 1 or i > 25:
        print(i)

Buggy submission (verdict: Runtime Error):

import time
st = time.time()

d = int(input())
clist = list(map(int,input().split()))
last_c = [0]*26
select_c = [0]*26
for i in range(26):
    select_c[i] = []

slist = [0] * d
for i in range(d):
    slist[i] = list(map(int,input().split()))

tlist = [0]*d
satisfy = [0]*(d+1)

#貪欲法
for i in range(0,d):
    max = 0
    max_n = 0
    for n in range(26):
        if i > 0:
            curr = slist[i][n] + satisfy[i-1]
        else:
            curr = slist[i][n]
        minus = 0
        for j in range(26):
            if n != j:
                minus -= clist[j] * (i - last_c[j])
        curr += minus
        if curr > max:
            max = curr
            max_n = n
    satisfy[i] = max
    last_c[max_n] = i+1 
    select_c[max_n].append(i+1)
    tlist[i] = max_n+1

import random
import numpy as np

sum = 0
total_c = 0


for i in range(d):
    sum += slist[i][tlist[i]-1]

ct = time.time()

for i in range(len(select_c)):
    start = 1
    c_change = 0
    if select_c[i] == []:
        c_change = np.sum(np.arange(d+1))
    else:
        for j in range(len(select_c[i])):
            end = select_c[i][j]
            c_change += np.sum(np.arange(end-start+1))
            start = end
        end = d+1
        c_change += np.sum(np.arange(end-start))
        start = end
    total_c += clist[i]*c_change

current_max = sum - total_c

import bisect
while ct-st < 1.9:
    change_d = random.randint(1,d)
    change_d_to_c = random.randint(0,len(select_c)-1)
    for x in range(len(select_c)):
        try:
            index = select_c[x].index(change_d)
            change = x
            s_change = slist[change_d-1][index]
            select_c[x].remove(change_d)
            break
        except:
            None

    s_change2 = slist[change_d-1][change_d_to_c]

    bisect.insort(select_c[change_d_to_c],change_d)
    #calc
    sum2 = sum - s_change + s_change2
    total_c2 = 0
    for i in range(len(select_c)):
        start = 1
        c_change = 0
        if select_c[i] == []:
            c_change = np.sum(np.arange(d+1))
        else:
            for j in range(len(select_c[i])):
                end = select_c[i][j]
                c_change += np.sum(np.arange(end-start+1))
                start = end
            end = d+1
            c_change += np.sum(np.arange(end-start))
            start = end
        total_c2 += clist[i]*c_change

    if sum - total_c < sum2 - total_c2:
        sum = sum2
        total_c = total_c2
        tlist[change_d-1] = change_d_to_c+1
    else:
        bisect.insort(select_c[change],change_d)
        select_c[change_d_to_c].remove(change_d)

    ct = time.time()
    
#remove first
for i in tlist:
    print(i)

Buggy submission (verdict: Runtime Error):

import time
st = time.time()

d = int(input())
clist = list(map(int,input().split()))
last_c = [0]*26
select_c = [0]*26
for i in range(26):
    select_c[i] = []

slist = [0] * d
for i in range(d):
    slist[i] = list(map(int,input().split()))

tlist = [0]*d
satisfy = [0]*(d+1)

#貪欲法
for i in range(0,d):
    max = 0
    max_n = 0
    for n in range(26):
        if i > 0:
            curr = slist[i][n] + satisfy[i-1]
        else:
            curr = slist[i][n]
        minus = 0
        for j in range(26):
            if n != j:
                minus -= clist[j] * (i - last_c[j])
        curr += minus
        if curr > max:
            max = curr
            max_n = n
    satisfy[i] = max
    last_c[max_n] = i+1 
    select_c[max_n].append(i+1)
    tlist[i] = max_n+1

import random
import numpy as np

sum = 0
total_c = 0


for i in range(d):
    sum += slist[i][tlist[i]-1]

ct = time.time()

for i in range(len(select_c)):
    start = 1
    c_change = 0
    if select_c[i] == []:
        c_change = np.sum(np.arange(d+1))
    else:
        for j in range(len(select_c[i])):
            end = select_c[i][j]
            c_change += np.sum(np.arange(end-start+1))
            start = end
        end = d+1
        c_change += np.sum(np.arange(end-start))
        start = end
    total_c += clist[i]*c_change

current_max = sum - total_c

import bisect
while ct-st < 1.9:
    change_d = random.randint(1,d)
    change_d_to_c = random.randint(0,len(select_c)-1)
    for x in range(len(select_c)):
        try:
            index = select_c[x].index(change_d)
            change = x
            s_change = slist[change_d-1][index]
            select_c[x].remove(change_d)
            break
        except:
            None

    s_change2 = slist[change_d-1][change_d_to_c]

    bisect.insort(select_c[change_d_to_c],change_d)
    #calc
    sum2 = sum - s_change + s_change2
    total_c2 = 0
    for i in range(len(select_c)):
        start = 1
        c_change = 0
        if select_c[i] == []:
            c_change = np.sum(np.arange(d+1))
        else:
            for j in range(len(select_c[i])):
                end = select_c[i][j]
                c_change += np.sum(np.arange(end-start+1))
                start = end
            end = d+1
            c_change += np.sum(np.arange(end-start))
            start = end
        total_c2 += clist[i]*c_change

    if sum - total_c < sum2 - total_c2:
        sum = sum2
        total_c = total_c2
        tlist[change_d-1] = change_d_to_c
    else:
        bisect.insort(select_c[change],change_d)
        select_c[change_d_to_c].remove(change_d)

    ct = time.time()
    
#remove first
for i in tlist:
    print(i)

Buggy submission (verdict: Runtime Error):
d = int(input())
clist = list(map(int,input().split()))
last_c = [0]*26
select_c = [0]*26
for i in range(26):
    select_c[i] = []

slist = [0] * d
for i in range(d):
    slist[i] = list(map(int,input().split()))

tlist = [0]*d
satisfy = [0]*(d+1)

#貪欲法
for i in range(0,d):
    max = 0
    max_n = 0
    for n in range(26):
        if i > 0:
            curr = slist[i][n] + satisfy[i-1]
        else:
            curr = slist[i][n]
        minus = 0
        for j in range(26):
            if n != j:
                minus -= clist[j] * (i - last_c[j])
        curr += minus
        if curr > max:
            max = curr
            max_n = n
    satisfy[i] = max
    last_c[max_n] = i+1 
    select_c[max_n].append(i+1)
    tlist[i] = max_n+1

import time
import random
import numpy as np

sum = 0
total_c = 0


for i in range(d):
    sum += slist[i][tlist[i]-1]

st = time.time()
ct = time.time()

for i in range(len(select_c)):
    start = 1
    c_change = 0
    if select_c[i] == []:
        c_change = np.sum(np.arange(d+1))
    else:
        for j in range(len(select_c[i])):
            end = select_c[i][j]
            c_change += np.sum(np.arange(end-start+1))
            start = end
        end = d+1
        c_change += np.sum(np.arange(end-start))
        start = end
    total_c += clist[i]*c_change

current_max = sum - total_c

import bisect
while ct-st < 1.9:
    change_d = random.randint(1,d)
    change_d_to_c = random.randint(0,len(select_c)-1)
    for x in range(len(select_c)):
        try:
            index = select_c[x].index(change_d)
            change = x
            s_change = slist[change_d-1][index]
            select_c[x].remove(change_d)
            break
        except:
            None

    s_change2 = slist[change_d-1][change_d_to_c]

    bisect.insort(select_c[change_d_to_c],change_d)
    #calc
    sum2 = sum - s_change + s_change2
    total_c2 = 0
    for i in range(len(select_c)):
        start = 1
        c_change = 0
        if select_c[i] == []:
            c_change = np.sum(np.arange(d+1))
        else:
            for j in range(len(select_c[i])):
                end = select_c[i][j]
                c_change += np.sum(np.arange(end-start+1))
                start = end
            end = d+1
            c_change += np.sum(np.arange(end-start))
            start = end
        total_c2 += clist[i]*c_change

    if sum - total_c < sum2 - total_c2:
        sum = sum2
        total_c = total_c2
        tlist[change_d-1] = change_d_to_c
    else:
        bisect.insort(select_c[change],change_d)
        select_c[change_d_to_c].remove(change_d)

    ct = time.time()
    
#remove first
for i in tlist:
    print(i)