結果
| 問題 |
No.2594 Mix shake!!
|
| コンテスト | |
| ユーザー |
 hitonanode
|
| 提出日時 | 2025-11-19 00:58:59 |
| 言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,130 bytes |
| コンパイル時間 | 243 ms |
| コンパイル使用メモリ | 12,672 KB |
| 実行使用メモリ | 11,648 KB |
| 最終ジャッジ日時 | 2025-11-19 00:59:06 |
| 合計ジャッジ時間 | 6,649 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 68 WA * 17 |
ソースコード
# Gemini 3.0
import sys
# Increase recursion depth just in case, though not used
sys.setrecursionlimit(2000)
def solve():
# Read all input from stdin
input = sys.stdin.read().split()
if not input:
return
iterator = iter(input)
try:
n = int(next(iterator))
a = []
for _ in range(n):
a.append(int(next(iterator)))
b = []
for _ in range(n):
b.append(int(next(iterator)))
c = []
for _ in range(n):
c.append(int(next(iterator)))
d = []
for _ in range(n):
d.append(int(next(iterator)))
except StopIteration:
return
# Verify totals match (Constraint from problem, but good sanity check)
sum_a = sum(a)
sum_b = sum(b)
sum_c = sum(c)
sum_d = sum(d)
if sum_a != sum_c or sum_b != sum_d:
print("No")
return
# Create Source and Target structures
# We need to track original indices for the subset condition.
# Stores: (apple, banana, total_vol, original_index)
sources = []
for i in range(n):
sources.append({
'a': a[i],
'b': b[i],
'vol': a[i] + b[i],
'id': i
})
targets = []
for i in range(n):
targets.append({
'a': c[i],
'b': d[i],
'vol': c[i] + d[i],
'id': i
})
# Sort by concentration of apple (a / vol) ascending.
# Comparison: a1/v1 < a2/v2 <=> a1*v2 < a2*v1
from functools import cmp_to_key
def compare_conc(item1, item2):
# a1 * (a2+b2) - a2 * (a1+b1)
# Simplify: a1/v1 vs a2/v2 -> a1*v2 vs a2*v1
val1 = item1['a'] * item2['vol']
val2 = item2['a'] * item1['vol']
if val1 < val2:
return -1
elif val1 > val2:
return 1
else:
return 0
sources.sort(key=cmp_to_key(compare_conc))
targets.sort(key=cmp_to_key(compare_conc))
# 1. Majorization Check (Lorenz Curve)
# Supply curve must be <= Demand curve (because Supply is sorted ascending, it's the 'most convex' boundary)
# We check at all breakpoints of both Supply and Demand.
# Collect all relevant volume checkpoints
checkpoints = set()
checkpoints.add(0)
curr_v = 0
for s in sources:
curr_v += s['vol']
checkpoints.add(curr_v)
curr_v = 0
for t in targets:
curr_v += t['vol']
checkpoints.add(curr_v)
sorted_checkpoints = sorted(list(checkpoints))
# Helper to compute accumulated apple at volume V for a sorted list of glasses
def get_acc_apple(glasses, query_vol):
apple_sum = 0
current_vol = 0
for g in glasses:
if current_vol >= query_vol:
break
remaining_needed = query_vol - current_vol
take_vol = min(remaining_needed, g['vol'])
# Add apple amount: take_vol * (g['a'] / g['vol'])
# We work with numerators to avoid float issues?
# But we need to return a value for comparison.
# Since we compare SumA_supply vs SumA_demand, let's keep it precise.
# We can return a fraction (numerator, denominator) or just use Python's large ints?
# Python floats (64-bit) might lose precision for 10^17 * 10^17.
# Let's return (numerator, denominator). Denominator is product of volumes? No, that grows too big.
# We can simply accumulate the raw value as a fraction class or decimal?
# Or better: We compare Sum1 vs Sum2.
# Sum1 = IntPart + FracPart.
# Actually, query_vol is always an integer (sum of inputs).
# take_vol is integer.
# g['a'] / g['vol'] is rational.
# We can simply perform the calculation using fractions.
term_num = take_vol * g['a']
term_den = g['vol']
# apple_sum += term_num / term_den
# To avoid creating huge common denominators, maybe keep as list of fractions?
# No, N=50. We can use Fraction class.
current_vol += take_vol
# Optimization: if taking full glass
if take_vol == g['vol']:
apple_sum += g['a'] # Integer addition
else:
# Partial
from fractions import Fraction
apple_sum += Fraction(term_num, term_den)
return apple_sum
# Perform checks
# Optimization: We can iterate through checkpoints and update sums incrementally.
# This avoids O(N^2) Fraction operations.
src_idx = 0
src_part_vol = 0 # How much of current source glass is used
src_acc_apple = 0
tgt_idx = 0
tgt_part_vol = 0
tgt_acc_apple = 0
# To handle the "fraction" part, we can keep acc_apple as Fraction
from fractions import Fraction
# Reset pointers for the loop
prev_v = 0
for v in sorted_checkpoints:
if v == 0:
continue
delta = v - prev_v
prev_v = v
# Advance Source
needed = delta
while needed > 0 and src_idx < n:
available = sources[src_idx]['vol'] - src_part_vol
take = min(needed, available)
# Add apple
term = Fraction(take * sources[src_idx]['a'], sources[src_idx]['vol'])
src_acc_apple += term
src_part_vol += take
needed -= take
if src_part_vol == sources[src_idx]['vol']:
src_idx += 1
src_part_vol = 0
# Advance Target
needed = delta
while needed > 0 and tgt_idx < n:
available = targets[tgt_idx]['vol'] - tgt_part_vol
take = min(needed, available)
term = Fraction(take * targets[tgt_idx]['a'], targets[tgt_idx]['vol'])
tgt_acc_apple += term
tgt_part_vol += take
needed -= take
if tgt_part_vol == targets[tgt_idx]['vol']:
tgt_idx += 1
tgt_part_vol = 0
# Check Condition: Supply <= Demand
if src_acc_apple > tgt_acc_apple:
print("No")
return
# 2. Subset Condition Check for Min and Max concentrations
# Due to the inability to swap contents without mixing, extreme concentration liquids
# must stay in their original containers (or move to containers that already have that concentration).
# Thus, the set of glasses required to have Min concentration must be a subset
# of the glasses initially having Min concentration. Same for Max.
def check_subset(is_min_check):
if is_min_check:
# Check Min
ref_conc_item = sources[0] # Lowest concentration source
# Find all sources with this concentration
src_ids = set()
for s in sources:
if compare_conc(s, ref_conc_item) == 0:
src_ids.add(s['id'])
else:
# Since sorted, we can break early?
# Yes, sources are sorted ascending.
break
# Find all targets with this concentration
# Note: If target asks for strictly LOWER concentration than source min,
# Majorization check would have failed.
# So we only care if target conc == source min conc.
tgt_ids = set()
for t in targets:
if compare_conc(t, ref_conc_item) == 0:
tgt_ids.add(t['id'])
elif compare_conc(t, ref_conc_item) < 0:
# Should have been caught by majorization, but for completeness:
# Impossible to create lower conc.
return False
return tgt_ids.issubset(src_ids)
else:
# Check Max
ref_conc_item = sources[-1] # Highest concentration source
src_ids = set()
# Iterate backwards
for i in range(n-1, -1, -1):
s = sources[i]
if compare_conc(s, ref_conc_item) == 0:
src_ids.add(s['id'])
else:
break
tgt_ids = set()
for t in targets:
if compare_conc(t, ref_conc_item) == 0:
tgt_ids.add(t['id'])
elif compare_conc(t, ref_conc_item) > 0:
return False
return tgt_ids.issubset(src_ids)
if not check_subset(True):
print("No")
return
if not check_subset(False):
print("No")
return
print("Yes")
if __name__ == '__main__':
solve()