Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import bisect


def main():
    n = input()
    aa = []
    xx = [-input()]
    for _ in xrange(n - 1):
        aa.append(-input())
    for a in aa:
        if a >= xx[-1]:
            xx.append(a)
        else:
            i = bisect.bisect_right(xx, a)
            if i == len(xx):
                i -= 1
            xx[i] = a
    print len(xx)


if __name__ == '__main__':
    main()


Fixed submission:
import bisect
 
 
def main():
    n = input()
    aa = []
    xx = [-input()]
    for _ in xrange(n - 1):
        aa.append(-input())
    for a in aa:
        if a >= xx[-1]:
            xx.append(a)
        else:
            i = bisect.bisect_right(xx, a)
            if i == len(xx):
                i -= 1
            xx[i] = a
    print len(xx)
 
 
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import heapq


def main():
    n = input()
    aa = []
    for _ in xrange(n):
        aa.append(input())
    xx = [aa.pop()]
    buf = []
    while aa:
        a = aa.pop()
        if a < xx[0]:
            heapq.heapreplace(xx, a)
        else:
            while xx and a >= xx[0]:
                heapq.heappush(buf, heapq.heappop(xx))
            if xx:
                heapq.heapreplace(xx, a)
                for b in buf:
                    heapq.heappush(xx, b)
                buf = []
            else:
                heapq.heappush(buf, a)
                xx = buf
                buf = []
    print len(xx)


if __name__ == '__main__':
    main()


Fixed submission:
import bisect
 
 
def main():
    n = input()
    aa = []
    xx = [-input()]
    for _ in xrange(n - 1):
        aa.append(-input())
    for a in aa:
        if a >= xx[-1]:
            xx.append(a)
        else:
            i = bisect.bisect_right(xx, a)
            if i == len(xx):
                i -= 1
            xx[i] = a
    print len(xx)
 
 
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):


def main():
    n = input()
    xy = []
    for _ in xrange(n):
        x, y = map(int, raw_input().split())
        xy.append([x, y])
    count = {}
    for i in xrange(n - 1):
        x0, y0 = xy[i]
        for j in xrange(i + 1, n):
            x1, y1 = xy[j]
            key = (x1 - x0, y1 - y0)
            try:
                count[key] += 1
            except KeyError:
                count[key] = 1
    print n - max(count.values())


if __name__ == '__main__':
    main()


Fixed submission:


def main():
    n = input()
    if n == 1:
        print 1
        return
    xy = []
    for _ in xrange(n):
        x, y = map(int, raw_input().split())
        xy.append([x, y])
    count = {}
    for i in xrange(n):
        x0, y0 = xy[i]
        for j in xrange(n):
            if i == j:
                continue
            x1, y1 = xy[j]
            key = (x1 - x0, y1 - y0)
            try:
                count[key] += 1
            except KeyError:
                count[key] = 1
    print n - max(count.values())


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):


def main():
    n = input()
    edges = []
    nodes = [0] * n
    children = {i: [] for i in xrange(n)}
    for _ in xrange(n - 1):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        edges.append([a, b])
        nodes[a] += 1
        nodes[b] += 1
        children[a].append(b)
        children[b].append(a)

    def search(i, deg, dist, visited):
        ret = []
        for j in children[i]:
            if nodes[j] < deg:
                return dist
            if nodes[j] > deg:
                continue
            if j in visited:
                continue
            visited.add(j)
            ret.append(search(j, deg, dist + 1, visited))
        if ret:
            return min(ret)
        else:
            return dist

    def key(i):
        deg = nodes[i]
        return deg, search(i, deg, 1, {i})

    nodes = sorted([node for node in xrange(n)],
                   key=lambda i: key(i))
    cc = map(int, raw_input().split())
    cc.sort()
    ans = [0] * n
    for node, c in zip(nodes, cc):
        ans[node] = c
    score = 0
    for a, b in edges:
        score += min(ans[a], ans[b])
    print score
    print ' '.join(map(str, ans))


if __name__ == '__main__':
    main()


Fixed submission:
import random
import sys
sys.setrecursionlimit(10**5 + 10)


def main():
    n = input()
    edges = []
    nodes = [0] * n
    children = {i: [] for i in xrange(n)}
    for _ in xrange(n - 1):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        edges.append([a, b])
        nodes[a] += 1
        nodes[b] += 1
        children[a].append(b)
        children[b].append(a)

    cc = map(int, raw_input().split())
    cc.sort(reverse=True)
    ans = [0] * n

    def dfs(node, visited):
        for nex in children[node]:
            if nex in visited:
                continue
            visited.add(nex)
            dfs(nex, visited)
        ans[node] = cc.pop()

    while True:
        start = random.randrange(n)
        if len(children[start]) > 1:
            break
    dfs(start, {start})

    score = 0
    for a, b in edges:
        score += min(ans[a], ans[b])
    print score
    print ' '.join(map(str, ans))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):

def main():
    n, m = map(int, raw_input().split())
    min_id = 1
    max_id = n
    for _ in xrange(m):
        l, r = map(int, raw_input().split())
        min_id = max(min_id, l)
        max_id = min(max_id, r)e
    print max(0, max_id - min_id + 1)


if __name__ == '__main__':
    main()


Fixed submission:

def main():
    n, m = map(int, raw_input().split())
    min_id = 1
    max_id = n
    for _ in xrange(m):
        l, r = map(int, raw_input().split())
        min_id = max(min_id, l)
        max_id = min(max_id, r)
    print max(0, max_id - min_id + 1)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
print {'A': 'T', 'T': 'A', 'G': 'C', 'C': 'G'}[input().strip()]

Fixed submission:
print {'A': 'T', 'T': 'A', 'G': 'C', 'C': 'G'}[raw_input().strip()]
Buggy python submission (verdict: Time Limit Exceeded):

def calc():
    a, b, c, d = map(int, raw_input().split())
    if a < b:
        return 'No'
    if d < b:
        return 'No'
    if c >= b:
        return 'Yes'
    a %= b
    s = set()
    while a not in s:
        s.add(a)
        a = (a + d) % b
        if a > c:
            return 'No'
    return 'Yes'


def main():
    t = input()
    for _ in range(t):
        print calc()


if __name__ == '__main__':
    main()


Fixed submission:

def gcd(a, b):
    if a < b:
        b, a = a, b
    while b:
        a, b = b, a % b
    return a


def calc():
    a, b, c, d = map(int, raw_input().split())
    if a < b:
        return 'No'
    if d < b:
        return 'No'
    if c >= b:
        return 'Yes'
    g = gcd(b, d)
    a %= b
    n = (b - a) / g
    if a + g * n == b:
        n -= 1
    if a + g * n > c:
        return 'No'
    else:
        return 'Yes'


def main():
    t = input()
    for _ in range(t):
        print calc()


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):


def main():
    n = int(input())
    pp = []
    for _ in range(n):
        pp.append(int(input()))

    xx = [None] * n
    for s in range(n - 1, -1, -1):
        if xx[s] is not None:
            continue
        count = 1
        pre = pp[s]
        for i in range(s+1, n):
            if pre + 1 == pp[i]:
                if xx[i] is not None:
                    xx[s] = xx[i] + count
                    break
                pre = pp[i]
                count += 1
        else:
            xx[s] = count
    print(n - max(xx))


if __name__ == '__main__':
    main()


Fixed submission:


def main():
    n = int(input())
    pp = []
    for _ in range(n):
        pp.append(int(input()))
    dd = {}
    for i in range(n):
        dd[pp[i]] = i

    xx = [-1] * n
    for s in range(n - 1, -1, -1):
        if xx[s] >= 0:
            continue
        count = 1
        pre = pp[s]
        while pre + 1 in dd and dd[pre + 1] > s:
            i = dd[pre + 1]
            if xx[i] >= 0:
                xx[s] = xx[i] + count
                break
            pre += 1
            count += 1
        else:
            xx[s] = count
    print(n - max(xx))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):


def main():
    string = input().strip()
    k = int(input())
    s = set()
    length = len(string)
    for i in range(length):
        for j in range(i, length):
            s.add(string[i:j+1])
    print(sorted(s)[k - 1])


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    string = input().strip()
    k = int(input())
    s = set()
    for char in sorted(set(string)):
        for i in range(len(string)):
            if string[i] == char:
                s.add(string[i])
                s.add(string[i:i+1])
                s.add(string[i:i+2])
                s.add(string[i:i+3])
                s.add(string[i:i+4])
                s.add(string[i:i+5])
        if len(s) >= k:
            print(sorted(s)[k - 1])
            return


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):


class UnionFind:

    def __init__(self, n):
        self.p = {i: i for i in range(n)}
        self.r = {i: 0 for i in range(n)}

    def root(self, x):
        if self.p[x] == x:
            return x
        self.p[x] = self.root(self.p[x])
        return self.p[x]

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.r[x] == self.r[y]:
            self.r[x] += 1
        elif self.r[x] > self.r[y]:
            x, y = y, x
        self.p[x] = y

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def cluster(self):
        c = {}
        for x in self.p:
            xx = self.root(x)
            if xx not in c:
                c[xx] = {x}
            else:
                c[xx].add(x)
        return c


def main():
    n, m = list(map(int, input().split()))
    pp = list(map(int, input().split()))
    uf = UnionFind(n)
    for _ in range(m):
        x, y = map(int, input().split())
        uf.merge(x - 1, y - 1)
    cc = uf.cluster()
    count = 0
    for clt in cc.values():
        p = set(pp[i] - 1 for i in clt)
        count += len(p & clt)
    print(count)


if __name__ == '__main__':
    main()


Fixed submission:


class UnionFind:

    def __init__(self, n):
        self.p = {i: i for i in range(n)}
        self.r = {i: 0 for i in range(n)}

    def root(self, x):
        if self.p[x] == x:
            return x
        self.p[x] = self.root(self.p[x])
        return self.p[x]

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.r[x] < self.r[y]:
            self.p[x] = y
        else:
            self.p[y] = x
            if self.r[x] == self.r[y]:
                self.r[x] += 1

    def cluster(self):
        c = {}
        for x in self.p:
            xx = self.root(x)
            if xx not in c:
                c[xx] = {x}
            else:
                c[xx].add(x)
        return c


def main():
    n, m = list(map(int, input().split()))
    pp = list(map(int, input().split()))
    uf = UnionFind(n)
    for _ in range(m):
        x, y = map(int, input().split())
        uf.merge(x - 1, y - 1)
    cc = uf.cluster()
    count = 0
    for clt in cc.values():
        p = set(pp[i] - 1 for i in clt)
        count += len(p & clt)
    print(count)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict


def main():
    h, w = map(int, input().split())
    s = []
    for _ in range(h):
        col = []
        s.append(col)
        for c in input().strip():
            col.append(ord(c))
    c_row = defaultdict(int)
    for col in s:
        c_row[tuple(sorted(col))] += 1
    if sum(c % 2 for c in c_row.values()) > h % 2:
        print('NO')
        return
    for row, c in c_row.items():
        if c % 2:
            count = defaultdict(int)
            for ch in row:
                count[ch] += 1
            if sum(cc % 2 for cc in count.values()) > w % 2:
                print('NO')
                return

    c_col = defaultdict(int)
    for col in zip(*s):
        c_col[tuple(sorted(col))] += 1
    if sum(c % 2 for c in c_col.values()) > w % 2:
        print('NO')
        return

    for col, c in c_col.items():
        if c % 2:
            count = defaultdict(int)
            for ch in col:
                count[ch] += 1
            if sum(cc % 2 for cc in count.values()) > h % 2:
                print('NO')
                return

    if s[0][0] == ord('b'):
        print('NO')
    else:
        print('YES')


main()


Fixed submission:
# -*- coding: utf-8 -*-

n = int(input())
xx = list([i, x] for i, x in enumerate(map(int, input().split())))
xx.sort(key=lambda x: x[1])

mid1 = xx[n // 2][1]
mid2 = xx[n // 2 - 1][1]
for i in range(n // 2):
    xx[i][1] = mid1
for i in range(n // 2, n):
    xx[i][1] = mid2

xx.sort()
print('\n'.join(str(x[1]) for x in xx))
Buggy python submission (verdict: Runtime Error):
def main():
    a, b = map(int, input().split())
    s, k = '.#'
    ans = [[k] * 100 for _ in range(50)] + [[s] * 100 for _ in range(50)]
    col = 0
    row = 0
    for _ in range(a - 1):
        ans[row][col] = s
        col += 2
        if col == 100:
            col = 0
            row += 2
    col = 0
    row = 99
    for _ in range(a - 1):
        ans[row][col] = k
        col += 2
        if col == 100:
            col = 0
            row -= 2
    print(100, 100)
    for row in ans:
        print(''.join(row))

if __name__ == '__main__':
    main()


Fixed submission:
def main():
    n = int(input())
    xx = [0] + list(map(int, input().split())) + [0]
    all_cost = sum(abs(xx[i+1] - xx[i]) for i in range(n+1))
    for i in range(n):
        a, b, c = xx[i:i+3]
        print(all_cost - abs(b - a) - abs(c - b) + abs(c - a))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
from math import acos, hypot, pi


class Point:
    def __init__(self, i, x, y):
        self.i = i
        self.x = int(x)
        self.y = int(y)


class Line:
    def __init__(self, p1, p2):
        self.p1 = p1
        self.p2 = p2
        self.d2 = (p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2
        if p1.x == p2.x:
            self.a = 1
            self.b = 0
        else:
            self.a = p2.y - p1.y
            self.b = p1.x - p2.x
        self.c = -p1.y * self.b - p1.x * self.a

    def dist(self, p):
        f = self.a * p.x + self.b * p.y + self.c
        if f == 0:
            d12 = (self.p1.x - p.x) ** 2 + (self.p1.y - p.y) ** 2
            d22 = (self.p2.x - p.x) ** 2 + (self.p2.y - p.y) ** 2
            if self.d2 < max(d12, d22):
                return None
            return 0
        if f < 0:
            return -1
        else:
            return 1

    def kaku(self, other):
        x = self.a * other.a + self.b * other.b
        x /= hypot(self.a, self.b) * hypot(other.a, other.b)
        return pi - acos(x)


def make_p(n, pp):
    pids = {p.i: [] for p in pp}
    for i in range(n):
        if len(pids[i]) == 2:
            continue
        p1 = pp[i]
        for j in pids:
            if i == j or len(pids[j]) == 2:
                continue
            p2 = pp[j]
            line = Line(p1, p2)
            ptype = {0: 0, 1: 0, -1: 0, None: 0}
            for k in pids:
                if k == i or k == j:
                    continue
                ptype[line.dist(pp[k])] += 1
            if ptype[None]:
                continue
            if ptype[1] == 0 or ptype[-1] == 0:
                pids[i].append(j)
                pids[j].append(i)
    return pids


def main():
    n = int(input())
    if n == 2:
        print(0.5)
        print(0.5)
        return
    pp = []
    for i in range(n):
        p = Point(i, *input().split())
        pp.append(p)
    pids = make_p(n, pp)
    prob = [0.0] * n
    for i, nei in pids.items():
        if len(nei) == 2:
            l1 = Line(pp[i], pp[nei[0]])
            l2 = Line(pp[i], pp[nei[1]])
            kaku = l1.kaku(l2)
            prob[i] += kaku / (2 * pi)
    for p in prob:
        print(p)


if __name__ == '__main__':
    main()


Fixed submission:

def score(s):
    return sum(map(int, s))


def main():
    s = input()
    best = score(s)
    for i in range(1, len(s)):
        ss = int(s) // 10**i * 10**i - 1
        best = max(best, score(str(ss)))
    print(best)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())

import math
def num_divisors_trial_division(n):
    num = 0
    for i in range(1, int(math.sqrt(n) + 1e-9) + 1):
        if n % i == 0:
            num += 1
            if n != i**2:
                num += 1
    
    return num

result = 0
for ab in range(1,n):
  tmp = num_divisors_trial_division(ab)
  result += tmp
print(result)

Fixed submission:
n=int(input())

def num_divisors_table(n):
    table = [0] * (n + 1)
    
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1
    
    return table

tmp = num_divisors_table(n-1)
print(sum(tmp))
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
lr=[list(map(int,input().split())) for _ in range(k)]

mod = 998244353

dp = [0] * (n+1)
sdp = [0] * (n+1)
dp[1] = 1
sdp[1] = 1

for i in range(n+1):
  for j in range(k):
    left = max(0, i-lr[j][1])
    right = max(0, i-lr[j][0]+1)
    
    dp[i] += sdp[right] - sdp[left]
  if i+1 <= n:
    sdp[i+1] = sdp[i]%mod + dp[i]%mod

print(dp%mod)

Fixed submission:
n,k=map(int,input().split())
lr=[list(map(int,input().split())) for _ in range(k)]

mod = 998244353

dp = [0] * (n+1)
sdp = [0] * (n+1)
dp[1] = 1
sdp[1] = 1

for i in range(n+1):
  for j in range(k):
    left = max(0, i-lr[j][1])
    right = max(0, i-lr[j][0]+1)
    
    dp[i] += sdp[right] - sdp[left]
  if i+1 <= n:
    sdp[i+1] = sdp[i]%mod + dp[i]%mod

print(dp[n]%mod)

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
S = {}
for i in range(k):
  tmp = list(map(int,input().split()))
  lr = range(tmp[0],tmp[1]+1)
  S = set(lr).union(S)

MOD = 998244353

dp = [0]*(n+1)
dp[1] = 1
for i in range(1,n+1):
  for j in S:
    if i-j > 0:
      dp[i] += dp[i-j]%MOD
print(dp[n]%MOD)

Fixed submission:
n,k=map(int,input().split())
lr=[list(map(int,input().split())) for _ in range(k)]

mod = 998244353

dp = [0] * (n+1)
sdp = [0] * (n+1)
dp[1] = 1
sdp[1] = 1

for i in range(n+1):
  for j in range(k):
    left = max(0, i-lr[j][1])
    right = max(0, i-lr[j][0]+1)
    
    dp[i] += sdp[right] - sdp[left]
  if i+1 <= n:
    sdp[i+1] = sdp[i]%mod + dp[i]%mod

print(dp[n]%mod)
Buggy python submission (verdict: Time Limit Exceeded):
n,x,m=map(int,input().split())

logn = (10**10).bit_length()
doubling = []
sumd = []
for _ in range(logn):
  tmpd = [-1] * m
  doubling.append(tmpd)
  tmps = [0] * m
  sumd.append(tmps)

for i in range(m):
  doubling[0][i] = i * i % m
  sumd[0][i] = i

for i in range(1,logn):
  for j in range(m):
    doubling[i][j] = doubling[i-1][doubling[i-1][j]]
    sumd[i][j] = sumd[i-1][j] + sumd[i-1][doubling[i-1][j]]

now = x
pos = 0
result = 0
while n:
  if n & 1:
    result += sumd[pos][now]
    now = doubling[pos][now]
  n = n >> 1
  pos += 1

print(result)


Fixed submission:
n,x,m=map(int,input().split())

logn = (10**10).bit_length()
doubling = []
sumd = []
for _ in range(logn):
  tmpd = [-1] * m
  doubling.append(tmpd)
  tmps = [0] * m
  sumd.append(tmps)

for i in range(m):
  doubling[0][i] = i * i % m
  sumd[0][i] = i

for i in range(1,logn):
  for j in range(m):
    doubling[i][j] = doubling[i-1][doubling[i-1][j]]
    sumd[i][j] = sumd[i-1][j] + sumd[i-1][doubling[i-1][j]]

now = x
pos = 0
result = 0
while n:
  if n & 1:
    result += sumd[pos][now]
    now = doubling[pos][now]
  n = n >> 1
  pos += 1

print(result)
Buggy python submission (verdict: Runtime Error):
  print('No')

Fixed submission:
d,t,s=map(int,input().split())

if d / s <= t:
  print('Yes')
else:
  print('No')
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))

from itertools import combinations

MOD = 10**9+7
result = 0
for seq in combinations(range(0, n), 2):
  result += a[seq[0]] * a[seq[1]] % MOD
print(result%MOD)


Fixed submission:
n=int(input())
a=list(map(int,input().split()))

s=[0]*(n+1)
for i in range(n):
  s[i+1] = s[i] + a[i]

MOD = 10**9+7
result = 0
for i in range(n):
  result += a[i]*(s[n] - s[i+1])%MOD
print(result%MOD)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))

MOD = 10**9+7
result = 0
for i in range(n-1):
  for j in range(i+1,n):
    result += a[i]*a[j] % MOD
print(result%MOD)



Fixed submission:
n=int(input())
a=list(map(int,input().split()))

s=[0]*(n+1)
for i in range(n):
  s[i+1] = s[i] + a[i]

MOD = 10**9+7
result = 0
for i in range(n):
  result += a[i]*(s[n] - s[i+1])%MOD
print(result%MOD)