Submission #754648

#	Time	Username	Problem	Language	Result	Execution time	Memory
754648		komalrajputtrootech	Programming Contest (POI11_pro)	Cpython 3	0 / 100	759 ms	9872 KiB

pro

import sys
from collections import defaultdict


def distributing_problems(contestant_problem_dict, problem_contestant_map, list_of_problems, prob_solving_time, total_duration):
    num_of_solved_prob = 0
    penalty_points = 0
    problem_solving_dict = defaultdict(list)
    for problem in list_of_problems:
        # find contestant who can solve the problem
        contestants_can_solve_problem = problem_contestant_map[problem]
        if not contestants_can_solve_problem:
            break
        selected_contestant = contestants_can_solve_problem[0]
        # # if there are more than two contestants who can solve the problem, select that contestant
        # # who can solve minimum problems
        if len(contestants_can_solve_problem) > 1:
            selected_dict = dict(
                filter(lambda item: item[0] in contestants_can_solve_problem, contestant_problem_dict.items()))
            min_val = min([len(selected_dict[ele]) for ele in selected_dict])
            for key, val in selected_dict.items():
                if len(val) == min_val:
                    selected_contestant = key
                    break

        if selected_contestant not in problem_solving_dict:
            # as this if first problem of contestant, starting time will be 0
            start_time = 0
        else:
            # to calculate total time spent by contestant, we add problem-solving time to
            # time of last problem solved
            start_time = problem_solving_dict[selected_contestant][-1][1] + prob_solving_time

        if (start_time + prob_solving_time) > total_duration:
            break

        problem_solving_dict[selected_contestant].append((problem, start_time))
        contestant_problem_dict[selected_contestant].remove(problem)
        if not contestant_problem_dict[selected_contestant]:
            del contestant_problem_dict[selected_contestant]
        penalty_points += start_time + prob_solving_time
        num_of_solved_prob += 1
    return num_of_solved_prob, penalty_points, problem_solving_dict


if __name__ == '__main__':
    contestant_problem_map = {}
    problem_contestant_map = {}
    num_of_con, num_of_prob, solving_time, duration, num_of_pairs = sys.stdin.readline().split()
    problem_list = set()
    # create a dictionary as which contestant can solve which problem
    for pair in range(int(num_of_pairs)):
        contestant, p = map(int, sys.stdin.readline().split())
        if contestant in contestant_problem_map.keys():
            contestant_problem_map[contestant].append(p)
        else:
            contestant_problem_map.update({
                contestant: [p]
            })

        if p in problem_contestant_map.keys() and contestant not in problem_contestant_map[p]:
            problem_contestant_map[p].append(contestant)
        else:
            problem_contestant_map.update({
                p: [contestant]
            })
        problem_list.add(p)
    num_of_problem_solved, penal_points, problems_solved_dict = distributing_problems(
        contestant_problem_map,
        problem_contestant_map,
        list(problem_list),
        int(solving_time),
        int(duration)
    )
    print(num_of_problem_solved, penal_points)
    lst = []
    for pnt, solved_problem in problems_solved_dict.items():
        for sol in solved_problem:
            print(pnt, sol[0], sol[1])

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10