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 sorted(list_of_problems, reverse=True):
# 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))
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 = sys.stdin.readline().split()
if contestant in contestant_problem_map.keys() and p not in contestant_problem_map[contestant]:
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)
print(contestant_problem_map)
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])
# for i in sorted(lst, key=lambda x: (x[2], x[0])):
# print(*i)
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
18 ms |
3412 KB |
Expected integer, but "{'1':" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
18 ms |
3284 KB |
Expected integer, but "{'1':" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
23 ms |
3604 KB |
Expected integer, but "{'1':" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
83 ms |
6100 KB |
Expected integer, but "{'1':" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
802 ms |
20496 KB |
Expected integer, but "{'1':" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
459 ms |
16464 KB |
Expected integer, but "{'1':" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1071 ms |
20752 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
88 ms |
6528 KB |
Expected integer, but "{'1':" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1081 ms |
17496 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
136 ms |
7900 KB |
Expected integer, but "{'1':" found |
2 |
Halted |
0 ms |
0 KB |
- |