Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def run(x, n, num_array):
    '''
    '''
    if len(num_array) == 0:
        print(x)
        return
    
    i = 0
    while True:
        if x - i not in num_array:
            print(x - i)
            return
        elif x + i not in num_array:
            print(x + i)
            return
        i += 1
        

if __name__ == '__main__':
    x, n = list(map(int, input().split()))
    num_array = list(map(int, input().split()))
    run(x, n, num_array)

Fixed submission:
def run(x):
    '''
    '''
    for i,v in enumerate(x):
        if v == 0:
            print(i+1)


if __name__ == '__main__':
    x = list(map(int, input().split()))
    run(x)

Buggy python submission (verdict: Runtime Error):
def run(x, n, num_array):
    '''
    '''
    if len(num_array) == 0:
        print(x)
        return
    
    i = 1
    while True:
        if x - i not in num_array:
            print(x - i)
            return
        if x + i not in num_array:
            print(x + i)
            return
        i += 1
        

if __name__ == '__main__':
    x, n = list(map(int, input().split()))
    num_array = list(map(int, input().split()))
    run(x, n, num_array)

Fixed submission:
def run(x):
    '''
    '''
    for i,v in enumerate(x):
        if v == 0:
            print(i+1)


if __name__ == '__main__':
    x = list(map(int, input().split()))
    run(x)

Buggy python submission (verdict: Runtime Error):
def run(x, n, num_array):
    '''
    '''
    if len(num_array) == 0:
        print(x)
        return
    
    i = 1
    while True:
        if x - i not in num_array:
            print(x - i)
            print('x-i: x={}, i={}'.format(x, i))
            return
        if x + i not in num_array:
            print(x + i)
            return
        i += 1
        

if __name__ == '__main__':
    x, n = list(map(int, input().split()))
    num_array = list(map(int, input().split()))
    run(x, n, num_array)

Fixed submission:
def run(x):
    '''
    '''
    for i,v in enumerate(x):
        if v == 0:
            print(i+1)


if __name__ == '__main__':
    x = list(map(int, input().split()))
    run(x)
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 15 17:30:06 2020

@author: divyarth
"""

import sys
import heapq
import math

#sys.setrecursionlimit(100000)
#input=sys.stdin.readline
#print=sys.stdout.write

from collections import deque
from collections import defaultdict
from collections import Counter

modH=int(10**9)+7
I=lambda : list(map(int,input().split(' ')))
def PRINT(lst,sep=' '): print(sep.join(map(str,lst)))

s=input()
stack=[]
mm=0
for i in range(len(s)):
    if s[i]=='R':
        stack.append('R')
    else:
        cnt=0
        while len(stack):
            stack.pop()
            cnt+=1
        mm=max(mm,cnt)        
cnt=0
while len(stack):
    stack.pop()
    cnt+=1
mm=max(mm,cnt)
print(mm)

    


Fixed submission:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 15 17:30:06 2020

@author: divyarth
"""

import sys
import heapq
import math

#sys.setrecursionlimit(100000)
#input=sys.stdin.readline
#print=sys.stdout.write

from collections import deque
from collections import defaultdict
from collections import Counter

modH=int(10**9)+7
I=lambda : list(map(int,input().split(' ')))
def PRINT(lst,sep=' '): print(sep.join(map(str,lst)))

s=input()
stack=[]
mm=0
for i in range(len(s)):
    if s[i]=='R':
        stack.append('R')
    else:
        cnt=0
        while len(stack):
            stack.pop()
            cnt+=1
        mm=max(mm,cnt)        
cnt=0
while len(stack):
    stack.pop()
    cnt+=1
mm=max(mm,cnt)
print(mm)
Buggy python submission (verdict: Time Limit Exceeded):
LI = lambda: list(map(int, input().split()))

N, K = LI()
P = LI()
C = LI()

INF = 10 ** 10


def all_minus():
    for c in C:
        if c > 0:
            return False
    return True


def main():
    if all_minus():
        ans = max(C)
        print(ans)
        return
        
    ans = -INF
    for i in range(N):
        w = [0]
        d = {i: 0}
        j = 1
        x = P[i] - 1
        while x not in d:
            d[x] = j
            w.append(w[j - 1] + C[x])
            x = P[x] - 1
            j += 1

        a, b = d[x], j
        for _ in range(b - a):
            w.append(w[-1] + C[x])
            x = P[x] - 1

        if K < 2 * b - a or w[b] - w[a] <= 0:
            v = max(w[:K + 1])
            ans = max(ans, v)
            continue
        
        v = w[a]
        k = K - a
        r = k // (b - a) - 1
        k -= r * (b - a)
        v += r * (w[b] - w[a])
        v += max(w[a : a + k + 1]) - w[a]
        ans = max(ans, v)
    print(ans)
        
                
if __name__ == "__main__":
    main()


Fixed submission:
LI = lambda: list(map(int, input().split()))

N, K = LI()
P = LI()
C = LI()

INF = 10 ** 10


def all_minus():
    for c in C:
        if c > 0:
            return False
    return True


def main():
    if all_minus():
        ans = max(C)
        print(ans)
        return
        
    ans = -INF
    for i in range(N):
        w = [0]
        d = {i: 0}
        j = 1
        x = P[i] - 1
        while x not in d:
            d[x] = j
            w.append(w[j - 1] + C[x])
            x = P[x] - 1
            j += 1

        a, b = d[x], j
        for _ in range(b - a):
            w.append(w[-1] + C[x])
            x = P[x] - 1

        if K < 2 * b - a or w[b] - w[a] <= 0:
            v = max(w[:K + 1])
            ans = max(ans, v)
            continue
        
        v = w[a]
        k = K - a
        r = k // (b - a) - 1
        k -= r * (b - a)
        v += r * (w[b] - w[a])
        v += max(w[a : a + k + 1]) - w[a]
        ans = max(ans, v)
    print(ans)
        
                
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import math
from heapq import heapify, heappop, heappush

LI = lambda: list(map(int, input().split()))

N, K = LI()
A = LI()


def main():
    hq = [(-a, -a, 1) for a in A]
    heapify(hq)
    for _ in range(K):
        x = heappop(hq)
        t = (x[1] / (x[2] + 1), x[1], x[2] + 1)
        heappush(hq, t)
    
    ans = math.ceil(-heappop(hq)[0])
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import math

LI = lambda: list(map(int, input().split()))

N, K = LI()
A = LI()


def judge(x):
    k = 0
    for a in A:
        if a <= x:
            continue
        if a % x == 0:
            k += a // x - 1
        else:
            k += a // x
    if k <= K:
        return True
    else:
        return False


def solve():
    left, right = 0, max(A)
    while right - left > 1:
        x = (left + right) // 2
        if judge(x):
            right = x
        else:
            left = x
    return right


def main():
    ans = solve()
    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import math
from heapq import heapify, heappop, heappush

LI = lambda: list(map(int, input().split()))

N, K = LI()
A = LI()


def main():
    hq = [(-a, -a, 1) for a in A]
    heapify(hq)
    for _ in range(K):
        x = heappop(hq)
        t = (x[1] / (x[2] + 1), x[1], x[2] + 1)
        heappush(hq, t)
    
    ans = math.ceil(-heappop(hq)[0])
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import math

LI = lambda: list(map(int, input().split()))

N, K = LI()
A = LI()


def judge(x):
    k = 0
    for a in A:
        if a <= x:
            continue
        if a % x == 0:
            k += a // x - 1
        else:
            k += a // x
    if k <= K:
        return True
    else:
        return False


def solve():
    left, right = 0, max(A)
    while right - left > 1:
        x = (left + right) // 2
        if judge(x):
            right = x
        else:
            left = x
    return right


def main():
    ans = solve()
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!python3

LI = lambda: list(map(int, input().split()))

# input
N = int(input())


def main():
    for i in range(1, N + 1):
        ans = 0
        xn = int(i ** 0.5) + 1
        for x in range(1, xn):
            s = i - x * x
            if s < 0:
                break
            yn = int(s ** 0.5) + 1
            for y in range(x, yn):
                t = s - (y * y + x * y)
                if t < 0:
                    break
                zn = int(t ** 0.5) + 1
                for z in range(y, zn):
                    v = z * (x + y + z)
                    if v == t:
                        n = len({x, y, z})                            
                        if n == 3:
                            ans += 6
                        elif n == 2:
                            ans += 3
                        else:
                            ans += 1
        print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N = int(input())

MAX = 10 ** 2


def main():
    l = [0] * (N + 1)
    for x in range(1, MAX + 1):
        for y in range(1, MAX + 1):
            for z in range(1, MAX + 1):
                v = (x + y + z) ** 2 - (x * y + y * z + z * x)
                if v <= N:
                    l[v] += 1
    for ans in l[1:]:
        print(ans)
        

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, K = LI()
A = LI()


def main():
    ans = A.copy()
    w = [0] * (N + 1)
    for i in range(N):
        w[max(0, i - A[i])] += 1
        w[min(N, i + A[i] + 1)] -= 1
    
    for _ in range(K):
        x = 0
        l = [0] * (N + 1)
        for i in range(N):
            x += w[i]
            ans[i] = x
            l[max(0, i - x)] += 1
            l[min(N, i + x + 1)] -= 1
        w = l
    
    print(*ans)


if __name__ == "__main__":
    main()


Fixed submission:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, K = LI()
A = LI()


def main():
    ans = A.copy()
    w = [0] * (N + 1)
    for i in range(N):
        w[max(0, i - A[i])] += 1
        w[min(N, i + A[i] + 1)] -= 1
    
    for _ in range(K):
        x = 0
        l = [0] * (N + 1)
        flag = True
        for i in range(N):
            x += w[i]
            if x != N:
                flag = False
            ans[i] = x
            l[max(0, i - x)] += 1
            l[min(N, i + x + 1)] -= 1
        if flag:
            break
        w = l
    
    print(*ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, S = LI()
A = LI()

MOD = 998244353


def main():
    dp = [0] * (S + 1)
    dp[0] = 1
    for i in range(N):
        dp, l = [0] * (S + 1), dp
        for j in range(S + 1):
            dp[j] = (dp[j] + 2 * l[j]) % MOD
            if A[i] + j <= S:
                dp[A[i] + j] = (dp[A[i] + j] + l[j]) % MOD
    
    ans = dp[-1]
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, S = LI()
A = LI()

MOD = 998244353


def main():
    dp = [0] * (S + 1)
    dp[0] = 1
    for i in range(N):
        dp, l = [0] * (S + 1), dp
        for j in range(S + 1):
            dp[j] = (dp[j] + 2 * l[j]) % MOD
            if A[i] + j <= S:
                dp[A[i] + j] = (dp[A[i] + j] + l[j]) % MOD
    
    ans = dp[-1]
    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef vector<vector<int>> vv;
typedef pair<int, int> P;


int N, S;
vector<ll> A;
map<ll, map<ll, ll>> m;
const ll MOD = 998244353;


void input() {
    cin >> N >> S;
    A = vector<ll>(N);
    rep(i, N) cin >> A[i];
}


int main() {
    input();
    m[0][0] += 1;
    for (int a : A) {
        for (int i = S - a; i >= 0; i--) {
            if (!m.count(i)) continue;
            for (auto p : m[i]) {
                m[a + i][p.first + 1] += p.second;
                m[a + i][p.first + 1] %= MOD;
            }
        }
    }

    vector<ll> p2(3001);
    p2[0] = 1;
    rep(i, 3000) p2[i + 1] = p2[i] * 2 % MOD;
    ll ans = 0;
    for (auto p : m[S]) {
        if (p.first == 0) continue;
        ll v = p.second * p2[N - p.first] % MOD;
        ans = (ans + v) % MOD;
    }
    cout << ans << endl;
}


Fixed submission:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, S = LI()
A = LI()

MOD = 998244353


def main():
    dp = [0] * (S + 1)
    dp[0] = 1
    for i in range(N):
        dp, l = [0] * (S + 1), dp
        for j in range(S + 1):
            dp[j] = (dp[j] + 2 * l[j]) % MOD
            if A[i] + j <= S:
                dp[A[i] + j] = (dp[A[i] + j] + l[j]) % MOD
    
    ans = dp[-1]
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
#!python3

# input
N, M = list(map(int, input().split()))

# odd
def solve1():
    assert False
    return [(i + 2, N - i) for i in range(M)]        


# even
def solve2():
    t = (N - 2) // 4
    l = [(i + 1, N - i) for i in range(t)]
    n = (N - 2) // 2 - t
    l = l + [(N // 2 + 1 + i, N // 2 - i) for i in range(n)]
    return l[:M]


def main():
    l = solve1() if N % 2 else solve2()
    for ans in l:
        print(*ans)
    

if __name__ == "__main__":
    main()


Fixed submission:
#!python3

# input
N, M = list(map(int, input().split()))

# odd
def solve1():
    return [(i + 2, N - i) for i in range(M)]        


# even
def solve2():
    t = (N - 2) // 4
    l = [(i + 2, N - i) for i in range(t)]
    n = (N - 2) // 2 - t
    l = l + [(N // 2 + 1 + i, N // 2 - i) for i in range(n)]
    return l[:M]


def main():
    l = solve1() if N % 2 else solve2()
    for ans in l:
        print(*ans)
    

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!python3

# input
N = int(input())
A = list(map(int, input().split()))


def main():
    P = [(A[i], i + 1) for i in range(N)]
    P.sort(reverse=True)

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for n, p in zip(range(1, N + 1), P):
        for i in range(n):
            j = n - 1 - i

            left = dp[i][j] + p[0] * abs(p[1] - (i + 1))
            dp[i + 1][j] = max(dp[i + 1][j], left)
            
            right = dp[i][j] + p[0] * abs(p[1] - (N - j))
            dp[i][j + 1] = max(dp[i][j + 1], right)

    ans = max([dp[i][N - i] for i in range(N)])
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
#!python3

# input
N = int(input())
A = list(map(int, input().split()))
# N = 2000
# A = [i for i in range(1, N + 1)]


def main():
    P = [(A[i], i + 1) for i in range(N)]
    P.sort(reverse=True)

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for n, p in zip(range(1, N + 1), P):
        x, y = p
        for i in range(n):
            j = n - 1 - i
            left = dp[i][j] + x * abs(y - (i + 1))
            dp[i + 1][j] = max(dp[i + 1][j], left)
            right = dp[i][j] + x * abs(y - (N - j))
            dp[i][j + 1] = max(dp[i][j + 1], right)

    ans = max([dp[i][N - i] for i in range(N)])
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!python3

# input
N, K = list(map(int, input().split()))


def main():
    x = N
    while True:
        y = max(x - K, K - x)
        if y < x:
            x = y
        else:
            break
    print(x)


if __name__ == "__main__":
    main()


Fixed submission:
#!python3

# input
N, K = list(map(int, input().split()))


def main():
    s = N % K
    ans = min(s, K - s)
    print(ans)    


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!python3

import itertools

import numpy as np


INF = 10 ** 5

# input
H, W, K = list(map(int, input().split()))
S = [input() for _ in range(H)]


def solve(w, l):
    n = len(l)
    x = np.zeros((n + 1, W), dtype=int)
    if n == 0:
        x[0] = w[-1]
    else:
        x[0] = w[l[0]]
        for i in range(1, n):
            x[i] = w[l[i]] - w[l[i-1]]
        x[-1] = w[-1] - w[l[-1]]
    if np.any(x > K):
        return INF
    ans = 0
    dp = x[:, 0]
    for i in range(1, W):
        dp += x[:, i]
        if np.any(dp > K):
            ans += 1
            dp = x[:, i]
    return ans


def main():
    w = np.array([[int(S[i][j]) for j in range(W)] for i in range(H)])
    w = np.cumsum(w, axis=0)

    ans = INF
    num_list = [i for i in range(H)]
    for i in range(H):
        comb_list = itertools.combinations(num_list, i)
        for l in comb_list:
            ans = min(ans, i + solve(w, l))

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
#!python3

import itertools


INF = 10 ** 5

# input
H, W, K = list(map(int, input().split()))
S = [[int(e) for e in input()] for _ in range(H)]


def solve(w, l):
    n = len(l) + 1
    ans = 0
    if n == 1:
        dp = 0
        for j in range(W):
            x = w[-1][j]
            if x > K:
                return INF
            dp += x
            if dp > K:
                ans += 1
                dp = x
    else:
        dp = [0] * n
        for j in range(W):
            x = [0] * n
            b = False
            for i in range(n):
                if i == 0:
                    x[i] = w[l[i]][j]
                elif i == n - 1:
                    x[i] = w[-1][j] - w[l[-1]][j]
                else:
                    x[i] = w[l[i]][j] - w[l[i-1]][j]
                if x[i] > K:
                    return INF
                dp[i] += x[i]
                if dp[i] > K:
                    b = True
            if b:
                dp = x
                ans += 1
    return ans


def main():
    w = [S[0]]
    for i in range(1, H):
        w.append([w[i-1][j] + S[i][j] for j in range(W)])

    ans = INF
    num_list = [i for i in range(H - 1)]
    for i in range(H):
        comb_list = itertools.combinations(num_list, i)
        for l in comb_list:
            ans = min(ans, i + solve(w, l))

    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import itertools

import numpy as np


# input
a = input()
b = input()
c = input()


def judge_array(x, y):
    l = [None] * 2001
    for i in range(2001):
        s = x[i:]
        t = y[:2001 - i]
        l[i] = np.all(np.where((s == t) | (s == 0) | (t == 0), True, False))
    return l


def main():
    n = [len(a), len(b), len(c)]
    d = {chr(ord('a') + i - 1): i for i in range(1, 27)}
    d['?'] = 0
    abc = np.full((3, 2001), np.zeros(2001))
    for i in range(2000):
        if i < n[0]:
            abc[0][i] = d[a[i]]
        if i < n[1]:
            abc[1][i] = d[b[i]]
        if i < n[2]:
            abc[2][i] = d[c[i]]

    w = [[None] * 3, [None] * 3, [None] * 3]
    for i in range(3):
        for j in range(3):
            if i == j:
                continue
            w[i][j] = judge_array(abc[i], abc[j])
    
    l = itertools.permutations([0, 1, 2])
    ans = 6000
    for x, y, z in l:
        xy = w[x][y]
        xz = w[x][z]
        yz = w[y][z]
        for i in range(2001):
            for j in range(2001):
                if xy[i] and yz[j] and xz[min(2000, i + j)]:
                    v = max(n[x], i + n[y], i + j + n[z])
                    ans = min(ans, v)
                    break
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
#!python3

import itertools

import numpy as np


# input
a = input()
b = input()
c = input()


def judge_array(x, y):
    l = [None] * 2001
    for i in range(2001):
        s = x[i:]
        t = y[:2001 - i]
        l[i] = np.all(np.where((s == t) | (s == 0) | (t == 0), True, False))
    return l


def main():
    n = [len(a), len(b), len(c)]
    d = {chr(ord('a') + i - 1): i for i in range(1, 27)}
    d['?'] = 0
    abc = np.full((3, 2001), np.zeros(2001))
    for i in range(2000):
        if i < n[0]:
            abc[0][i] = d[a[i]]
        if i < n[1]:
            abc[1][i] = d[b[i]]
        if i < n[2]:
            abc[2][i] = d[c[i]]

    w = [[None] * 3, [None] * 3, [None] * 3]
    for i in range(3):
        for j in range(3):
            if i == j:
                continue
            w[i][j] = judge_array(abc[i], abc[j])
    
    l = itertools.permutations([0, 1, 2])
    ans = 6000
    for x, y, z in l:
        xy = w[x][y]
        xz = w[x][z]
        yz = w[y][z]
        for i in range(2001):
            for j in range(2001):
                if xy[i] and yz[j] and xz[min(2000, i + j)]:
                    v = max(n[x], i + n[y], i + j + n[z])
                    ans = min(ans, v)
                    break
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

LI = lambda: list(map(int, input().split()))

N = int(input())
XD = [LI() for _ in range(N)]

MOD = 998244353


class BIT:

    def __init__(self, n):
        self.n = n
        self.dat = [i - 1 for i in range(self.n + 1)]

    def change(self, i, x):
        i += 1
        while i <= self.n:
            self.dat[i] = max(self.dat[i], x)
            i += i & -i

    def max_num(self, i):
        if i == 0:
            return -1
        return max(self.dat[i], self.max_num(i - (i & -i)))


def main():
    XD.sort()
    x = [None] * N
    d = [None] * N
    for i in range(N):
        x[i], d[i] = XD[i]
    
    bit = BIT(N)
    w = [None] * N
    for i in range(N - 1, -1, -1):
        v = x[i] + d[i]
        j = bit.max_num(bisect.bisect_left(x, v))
        w[i] = j - i
        bit.change(i, j)
    
    dp = [None] * (N + 1)
    dp[-1] = 1
    for i in range(N - 1, -1, -1):
        dp[i] = (dp[i + 1] + dp[i + w[i] + 1]) % MOD
    
    ans = dp[0]
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import bisect

LI = lambda: list(map(int, input().split()))

N = int(input())
XD = [LI() for _ in range(N)]

MOD = 998244353


class BIT:

    def __init__(self, n):
        self.n = n
        self.dat = [i - 1 for i in range(self.n + 1)]

    def change(self, i, x):
        i += 1
        while i <= self.n:
            self.dat[i] = max(self.dat[i], x)
            i += i & -i

    def max_num(self, i):
        if i == 0:
            return -1
        return max(self.dat[i], self.max_num(i - (i & -i)))


def main():
    XD.sort()
    x = [None] * N
    d = [None] * N
    for i in range(N):
        x[i], d[i] = XD[i]
    
    bit = BIT(N)
    w = [None] * N
    for i in range(N - 1, -1, -1):
        v = x[i] + d[i]
        j = bit.max_num(bisect.bisect_left(x, v))
        w[i] = j - i
        bit.change(i, j)
    
    dp = [None] * (N + 1)
    dp[-1] = 1
    for i in range(N - 1, -1, -1):
        dp[i] = (dp[i + 1] + dp[i + w[i] + 1]) % MOD
    
    ans = dp[0]
    print(ans)


if __name__ == "__main__":
    main()