问题

### Instructions: You are an expert Python programmer. You will be given a question (problem specification) and will generate a correct Python program that matches the specification and passes all tests. You will NOT return anything except for the program.
### Question:
Takahashi will embark on an adventure.
During the adventure, N events will occur.
The i-th event (1\leq i\leq N) is represented by a pair of integers (t _ i,x _ i) (1\leq t _ i\leq 2,1\leq x _ i\leq N) and is as follows:

- If t _ i=1, he finds one potion of type x _ i. He can choose to pick it up or discard it.
- If t _ i=2, he encounters one monster of type x _ i. If he has a potion of type x _ i, he can use one to defeat the monster. If he does not defeat it, he will be defeated.

Determine whether he can defeat all the monsters without being defeated.
If he cannot defeat all the monsters, print -1.
Otherwise, let K be the maximum number of potions he has at some point during the adventure.
Let K _ {\min} be the minimum value of K across all strategies where he will not be defeated.
Print the value of K _ {\min} and the actions of Takahashi that achieve K _ {\min}.

Input

The input is given from Standard Input in the following format:
N
t _ 1 x _ 1
t _ 2 x _ 2
\vdots
t _ N x _ N

Output

If Takahashi cannot defeat all the monsters, print -1.
If he can, print the value of K _ {\min} in the first line, and in the second line, for each i such that t _ i=1 in ascending order, print 1 if he picks up the potion found at the i-th event, and 0 otherwise, separated by spaces.
If multiple sequences of actions achieve K _ {\min} and allow him to finish the adventure without being defeated, you may print any of them.

Constraints


- 1\leq N\leq2\times10^5
- 1\leq t _ i\leq2\ (1\leq i\leq N)
- 1\leq x _ i\leq N\ (1\leq i\leq N)
- All input values are integers.

Sample Input 1

13
1 2
1 3
1 1
1 3
1 2
2 3
1 3
1 3
2 3
1 3
2 2
2 3
2 1

Sample Output 1

3
1 1 1 0 0 1 0 1

The sample output corresponds to the following actions:

- Find potions of types 2,3,1 in this order. Pick up all of them.
- Find potions of types 3,2 in this order. Do not pick up any of them.
- Encounter a type-3 monster. Use one type-3 potion to defeat it.
- Find a type-3 potion. Pick it up.
- Find a type-3 potion. Do not pick it up.
- Encounter a type-3 monster. Use one type-3 potion to defeat it.
- Find a type-3 potion. Pick it up.
- Encounter a type-2 monster. Use one type-2 potion to defeat it.
- Encounter a type-3 monster. Use one type-3 potion to defeat it.
- Encounter a type-1 monster. Use one type-1 potion to defeat it.

In this sequence of actions, the value of K is 3.
There is no way to avoid defeat with K\leq 2, so the sought value of K _ {\min} is 3.
There are multiple sequences of actions that satisfy K=3 and allow him to avoid defeat; you may print any of them.

Sample Input 2

4
2 3
1 4
2 1
1 2

Sample Output 2

-1

He will inevitably be defeated by the first monster he encounters.

Sample Input 3

30
1 25
1 2
1 10
1 18
2 18
1 11
2 11
1 21
1 6
2 2
2 10
1 11
1 24
1 11
1 3
1 2
1 18
2 25
1 8
1 10
1 11
2 18
2 10
1 10
2 2
1 24
1 10
2 10
1 25
2 6

Sample Output 3

4
1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0

### Format: Read the inputs from stdin solve the problem and write the answer to stdout (do not directly test on the sample inputs). Enclose your code within delimiters as follows.
```python
# YOUR CODE HERE
```

### Answer: (use the provided format with backticks)

答案

模型 模型答案 正确答案
金声玉亮2.0 ```python
import sys
from collections import defaultdict

def main():
input = sys.stdin.read
data = input().split()

N = int(data[0])
events = []
for i in range(N):
events.append((int(data[2 * i + 1]), int(data[2 * i + 2])))

def can_defeat_all_monsters(events):
potions = defaultdict(int)
max_potions = 0
actions = []

for t, x in events:
if t == 1:
potions[x] += 1
actions.append(1)
max_potions = max(max_potions, sum(potions.values()))
elif t == 2:
if potions[x] > 0:
potions[x] -= 1
else:
return -1, []

return max_potions, actions

def minimize_potions(events):
potions = defaultdict(int)
max_potions = 0
actions = []

for t, x in events:
if t == 1:
if potions[x] == 0:
potions[x] += 1
actions.append(1)
max_potions = max(max_potions, sum(potions.values()))
else:
actions.append(0)
elif t == 2:
if potions[x] > 0:
potions[x] -= 1
else:
return -1, []

return max_potions, actions

max_potions, actions = minimize_potions(events)

if max_potions == -1:
print(-1)
else:
print(max_potions)
print(' '.join(map(str, actions)))

if __name__ == "__main__":
main()
```		 [{"input": "13\n1 2\n1 3\n1 1\n1 3\n1 2\n2 3\n1 3\n1 3\n2 3\n1 3\n2 2\n2 3\n2 1\n", "output": "3\n1 1 1 0 0 1 0 1\n", "testtype": "stdin"}, {"input": "4\n2 3\n1 4\n2 1\n1 2\n", "output": "-1\n", "testtype": "stdin"}, {"input": "30\n1 25\n1 2\n1 10\n1 18\n2 18\n1 11\n2 11\n1 21\n1 6\n2 2\n2 10\n1 11\n1 24\n1 11\n1 3\n1 2\n1 18\n2 25\n1 8\n1 10\n1 11\n2 18\n2 10\n1 10\n2 2\n1 24\n1 10\n2 10\n1 25\n2 6\n", "output": "4\n1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0\n", "testtype": "stdin"}]
deepseek-r1

```python
import bisect
from collections import defaultdict

def main():
import sys
input = sys.stdin.read().split()
idx = 0
N = int(input[idx])
idx +=1
events = []
for i in range(N):
t = int(input[idx])
x = int(input[idx+1])
idx +=2
events.append({'t': t, 'x': x, 'position': i+1})

potions = defaultdict(list)
monsters = defaultdict(list)
for event in events:
if event['t'] == 1:
potions[event['x']].append(event['position'])
else:
monsters[event['x']].append(event['position'])

# Feasibility check
feasible = True
for x in monsters:
m_list = monsters[x]
p_list = potions.get(x, [])
if len(p_list) < len(m_list):
feasible = False
break
for j in range(len(m_list)):
m_pos = m_list[j]
required = j + 1
cnt = bisect.bisect_right(p_list, m_pos)
if cnt < required:
feasible = False
break
if not feasible:
break
if not feasible:
print(-1)
return

required_potions = set()

# Assign potions to monsters
for x in monsters:
p_list = potions[x]
m_list = monsters[x]
ptr = len(p_list) - 1
# Process monsters in reverse order
for m_pos in reversed(m_list):
low = 0
high = ptr
best = -1
# Find the latest potion <= m_pos and <= ptr
while low <= high:
mid = (low + high) // 2
if p_list[mid] <= m_pos:
best = mid
low = mid + 1
else:
high = mid - 1
required_potions.add(p_list[best])
ptr = best - 1

# Also check for x in potions where there are monsters
# Add required potions for x=1's monster
for x in monsters:
m_list = monsters[x]
p_list = potions.get(x, [])
if not p_list:
continue

# Simulate to compute K_min
current_potions = 0
max_k = 0
for event in events:
if event['t'] == 1:
if event['position'] in required_potions:
current_potions +=1
if current_potions > max_k:
max_k = current_potions
else:
current_potions -=1

# Generate output actions
output_actions = []
for event in events:
if event['t'] == 1:
if event['position'] in required_potions:
output_actions.append('1')
else:
output_actions.append('0')

print(max_k)
print(' '.join(output_actions))

if __name__ == '__main__':
main()
```		 [{"input": "13\n1 2\n1 3\n1 1\n1 3\n1 2\n2 3\n1 3\n1 3\n2 3\n1 3\n2 2\n2 3\n2 1\n", "output": "3\n1 1 1 0 0 1 0 1\n", "testtype": "stdin"}, {"input": "4\n2 3\n1 4\n2 1\n1 2\n", "output": "-1\n", "testtype": "stdin"}, {"input": "30\n1 25\n1 2\n1 10\n1 18\n2 18\n1 11\n2 11\n1 21\n1 6\n2 2\n2 10\n1 11\n1 24\n1 11\n1 3\n1 2\n1 18\n2 25\n1 8\n1 10\n1 11\n2 18\n2 10\n1 10\n2 2\n1 24\n1 10\n2 10\n1 25\n2 6\n", "output": "4\n1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE
import sys
import threading
def main():
import sys
import math
sys.setrecursionlimit(1 << 25)
N = int(sys.stdin.readline())
events = []
potion_indices = {}
monster_indices = {}
t_list = []
x_list = []
pick_up_indices = []
action_indices = []
for idx in range(N):
t_i, x_i = sys.stdin.readline().split()
t_i = int(t_i)
x_i = int(x_i)
events.append((t_i, x_i))
t_list.append(t_i)
x_list.append(x_i)
if t_i == 1:
if x_i not in potion_indices:
potion_indices[x_i] = []
potion_indices[x_i].append(idx)
pick_up_indices.append(idx)
elif t_i ==2:
if x_i not in monster_indices:
monster_indices[x_i] = []
monster_indices[x_i].append(idx)
action = [0]*len(pick_up_indices)
possible = True
max_potions = 0
from collections import deque, defaultdict
carry = defaultdict(int)
total_potions = 0
K = 0
# For each type x, match potions to monsters
for x in monster_indices:
if x not in potion_indices or len(potion_indices[x]) < len(monster_indices[x]):
print(-1)
return
potions = potion_indices[x]
monsters = monster_indices[x]
i = len(potions)-1
j = len(monsters)-1
while j>=0:
while i>=0 and potions[i]>=monsters[j]:
i-=1
if i<0:
print(-1)
return
# Assign potion at potions[i] to monster at monsters[j]
pickup_idx = potions[i]
action_idx = pick_up_indices.index(pickup_idx)
action[action_idx]=1
i-=1
j-=1
# For remaining potions, we can choose not to pick them up
# Now simulate events to compute K
carry = defaultdict(int)
total_potions = 0
K = 0
action_ptr = 0
for idx in range(N):
t_i, x_i = events[idx]
if t_i == 1:
if action[action_ptr]:
carry[x_i] +=1
total_potions +=1
if total_potions > K:
K = total_potions
action_ptr +=1
elif t_i == 2:
if carry[x_i]>0:
carry[x_i]-=1
total_potions -=1
else:
# Should not happen as per assignment
print(-1)
return
print(K)
print(' '.join(map(str, action)))
threading.Thread(target=main).start()
```		 [{"input": "13\n1 2\n1 3\n1 1\n1 3\n1 2\n2 3\n1 3\n1 3\n2 3\n1 3\n2 2\n2 3\n2 1\n", "output": "3\n1 1 1 0 0 1 0 1\n", "testtype": "stdin"}, {"input": "4\n2 3\n1 4\n2 1\n1 2\n", "output": "-1\n", "testtype": "stdin"}, {"input": "30\n1 25\n1 2\n1 10\n1 18\n2 18\n1 11\n2 11\n1 21\n1 6\n2 2\n2 10\n1 11\n1 24\n1 11\n1 3\n1 2\n1 18\n2 25\n1 8\n1 10\n1 11\n2 18\n2 10\n1 10\n2 2\n1 24\n1 10\n2 10\n1 25\n2 6\n", "output": "4\n1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0\n", "testtype": "stdin"}]
gpt-4o-2024-08-06 ```python
# YOUR CODE HERE
def main():
import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
events = [(int(data[2 * i + 1]), int(data[2 * i + 2])) for i in range(N)]

potions = {}
actions = []
max_potions = 0

for t, x in events:
if t == 1:
# Event is finding a potion of type x
if x not in potions:
potions[x] = 0
potions[x] += 1
actions.append(1)
max_potions = max(max_potions, potions[x])
elif t == 2:
# Event is encountering a monster of type x
if x not in potions or potions[x] == 0:
print(-1)
return
potions[x] -= 1

# Now we need to find the minimum K that allows us to defeat all monsters
# We will simulate the process again, but this time we will try to minimize the max_potions
potions = {}
actions = []
current_potions = 0
min_K = max_potions

for t, x in events:
if t == 1:
# Event is finding a potion of type x
if x not in potions:
potions[x] = 0
if current_potions < min_K:
potions[x] += 1
current_potions += 1
actions.append(1)
else:
actions.append(0)
elif t == 2:
# Event is encountering a monster of type x
if potions[x] > 0:
potions[x] -= 1
current_potions -= 1

print(min_K)
print(' '.join(map(str, actions)))

main()
```		 [{"input": "13\n1 2\n1 3\n1 1\n1 3\n1 2\n2 3\n1 3\n1 3\n2 3\n1 3\n2 2\n2 3\n2 1\n", "output": "3\n1 1 1 0 0 1 0 1\n", "testtype": "stdin"}, {"input": "4\n2 3\n1 4\n2 1\n1 2\n", "output": "-1\n", "testtype": "stdin"}, {"input": "30\n1 25\n1 2\n1 10\n1 18\n2 18\n1 11\n2 11\n1 21\n1 6\n2 2\n2 10\n1 11\n1 24\n1 11\n1 3\n1 2\n1 18\n2 25\n1 8\n1 10\n1 11\n2 18\n2 10\n1 10\n2 2\n1 24\n1 10\n2 10\n1 25\n2 6\n", "output": "4\n1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0\n", "testtype": "stdin"}]
Qwen2-72B-Instruct ```python
from collections import defaultdict
import heapq

N = int(input())
events = [list(map(int, input().split())) for _ in range(N)]

potion_counts = defaultdict(int)
max_potions = 0
actions = []
pq = []

for i, (t, x) in enumerate(events):
if t == 1:
if potion_counts[x] < max_potions:
actions.append(1)
potion_counts[x] += 1
heapq.heappush(pq, x)
max_potions += 1
else:
actions.append(0)
elif t == 2:
if potion_counts[x] > 0:
potion_counts[x] -= 1
elif pq:
potion_to_discard = heapq.heappop(pq)
potion_counts[potion_to_discard] -= 1
max_potions -= 1
else:
print(-1)
return

print(max_potions)
print(' '.join(map(str, actions)))
```
```		 [{"input": "13\n1 2\n1 3\n1 1\n1 3\n1 2\n2 3\n1 3\n1 3\n2 3\n1 3\n2 2\n2 3\n2 1\n", "output": "3\n1 1 1 0 0 1 0 1\n", "testtype": "stdin"}, {"input": "4\n2 3\n1 4\n2 1\n1 2\n", "output": "-1\n", "testtype": "stdin"}, {"input": "30\n1 25\n1 2\n1 10\n1 18\n2 18\n1 11\n2 11\n1 21\n1 6\n2 2\n2 10\n1 11\n1 24\n1 11\n1 3\n1 2\n1 18\n2 25\n1 8\n1 10\n1 11\n2 18\n2 10\n1 10\n2 2\n1 24\n1 10\n2 10\n1 25\n2 6\n", "output": "4\n1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0\n", "testtype": "stdin"}]
DeepSeek-Coder-V2-Lite-Instruct ```python
# YOUR CODE HERE
import sys
from collections import defaultdict

def read_ints():
return list(map(int, sys.stdin.readline().strip().split()))

# Read input
N = int(sys.stdin.readline().strip())
events = [read_ints() for _ in range(N)]

# Initialize variables
potion_count = defaultdict(int)
actions = []

# Process events
for t, x in events:
if t == 1:
# Find a potion
potion_count[x] += 1
actions.append(1)
elif t == 2:
# Encounter a monster
if potion_count[x] > 0:
potion_count[x] -= 1
actions.append(0)
else:
# Cannot defeat the monster
print(-1)
sys.exit()

# Calculate the minimum K_min
K_min = max(potion_count.values())

# Print the result
print(K_min)
print(' '.join(map(str, actions)))
```		 [{"input": "13\n1 2\n1 3\n1 1\n1 3\n1 2\n2 3\n1 3\n1 3\n2 3\n1 3\n2 2\n2 3\n2 1\n", "output": "3\n1 1 1 0 0 1 0 1\n", "testtype": "stdin"}, {"input": "4\n2 3\n1 4\n2 1\n1 2\n", "output": "-1\n", "testtype": "stdin"}, {"input": "30\n1 25\n1 2\n1 10\n1 18\n2 18\n1 11\n2 11\n1 21\n1 6\n2 2\n2 10\n1 11\n1 24\n1 11\n1 3\n1 2\n1 18\n2 25\n1 8\n1 10\n1 11\n2 18\n2 10\n1 10\n2 2\n1 24\n1 10\n2 10\n1 25\n2 6\n", "output": "4\n1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0\n", "testtype": "stdin"}]
Meta-Llama-3.1-405B-Instruct-Turbo ```python
import sys
from collections import defaultdict

def solve():
N = int(input())
events = []
for _ in range(N):
t, x = map(int, input().split())
events.append((t, x))

potions = defaultdict(int)
max_potions = 0
actions = []
for t, x in events:
if t == 1:
potions[x] += 1
max_potions = max(max_potions, sum(potions.values()))
actions.append(1)
else:
if potions[x] == 0:
print(-1)
return
potions[x] -= 1

print(max_potions)
print(*actions)

if __name__ == "__main__":
solve()
```		 [{"input": "13\n1 2\n1 3\n1 1\n1 3\n1 2\n2 3\n1 3\n1 3\n2 3\n1 3\n2 2\n2 3\n2 1\n", "output": "3\n1 1 1 0 0 1 0 1\n", "testtype": "stdin"}, {"input": "4\n2 3\n1 4\n2 1\n1 2\n", "output": "-1\n", "testtype": "stdin"}, {"input": "30\n1 25\n1 2\n1 10\n1 18\n2 18\n1 11\n2 11\n1 21\n1 6\n2 2\n2 10\n1 11\n1 24\n1 11\n1 3\n1 2\n1 18\n2 25\n1 8\n1 10\n1 11\n2 18\n2 10\n1 10\n2 2\n1 24\n1 10\n2 10\n1 25\n2 6\n", "output": "4\n1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0\n", "testtype": "stdin"}]
Meta-Llama-3.1-70B-Instruct-Turbo ```python
import sys
from collections import defaultdict

def solve():
n = int(input())
events = []
for _ in range(n):
t, x = map(int, input().split())
events.append((t, x))

monster = defaultdict(int)
for t, x in events:
if t == 2:
monster[x] += 1

pick = [0] * n
potions = defaultdict(int)
max_potions = 0
for i, (t, x) in enumerate(events):
if t == 1:
if monster[x] > 0:
pick[i] = 1
potions[x] += 1
monster[x] -= 1
elif len(potions) < max_potions:
pick[i] = 1
potions[x] += 1
else:
if potions[x] == 0:
print(-1)
return
potions[x] -= 1
max_potions = max(max_potions, len(potions))

print(max_potions)
print(*pick)

if __name__ == "__main__":
solve()
```		 [{"input": "13\n1 2\n1 3\n1 1\n1 3\n1 2\n2 3\n1 3\n1 3\n2 3\n1 3\n2 2\n2 3\n2 1\n", "output": "3\n1 1 1 0 0 1 0 1\n", "testtype": "stdin"}, {"input": "4\n2 3\n1 4\n2 1\n1 2\n", "output": "-1\n", "testtype": "stdin"}, {"input": "30\n1 25\n1 2\n1 10\n1 18\n2 18\n1 11\n2 11\n1 21\n1 6\n2 2\n2 10\n1 11\n1 24\n1 11\n1 3\n1 2\n1 18\n2 25\n1 8\n1 10\n1 11\n2 18\n2 10\n1 10\n2 2\n1 24\n1 10\n2 10\n1 25\n2 6\n", "output": "4\n1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0\n", "testtype": "stdin"}]
baichuan4 ```python
from collections import defaultdict

def main():
n = int(input())
events = [tuple(map(int, input().split())) for _ in range(n)]

# Initialize dictionaries to keep track of potions and monsters
potions = defaultdict(int)
monsters = defaultdict(int)

# Process events
for t, x in events:
if t == 1: # Found a potion
potions[x] += 1
elif t == 2: # Encountered a monster
if potions[x] > 0: # Defeat the monster with a potion
potions[x] -= 1
else: # No potion to defeat the monster
print(-1)
return

# Calculate the minimum number of potions needed at any time
k_min = max(potions.values())

# Generate a sequence of actions that achieves k_min
actions = []
for t, x in events:
if t == 1: # Found a potion
if potions[x] < k_min:
actions.append(1) # Pick up the potion
potions[x] += 1
else:
actions.append(0) # Do not pick up the potion
elif t == 2: # Encountered a monster
# Since we've already processed the events, we know there's a potion to defeat the monster
pass

# Print the result
print(k_min)
print(' '.join(map(str, actions)))

if __name__ == "__main__":
main()
```		 [{"input": "13\n1 2\n1 3\n1 1\n1 3\n1 2\n2 3\n1 3\n1 3\n2 3\n1 3\n2 2\n2 3\n2 1\n", "output": "3\n1 1 1 0 0 1 0 1\n", "testtype": "stdin"}, {"input": "4\n2 3\n1 4\n2 1\n1 2\n", "output": "-1\n", "testtype": "stdin"}, {"input": "30\n1 25\n1 2\n1 10\n1 18\n2 18\n1 11\n2 11\n1 21\n1 6\n2 2\n2 10\n1 11\n1 24\n1 11\n1 3\n1 2\n1 18\n2 25\n1 8\n1 10\n1 11\n2 18\n2 10\n1 10\n2 2\n1 24\n1 10\n2 10\n1 25\n2 6\n", "output": "4\n1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0\n", "testtype": "stdin"}]
doubao ```python
n = int(input())
events = [tuple(map(int, input().split())) for _ in range(n)]

pots = {}
k_min = float('inf')
actions = []

for t, x in events:
if t == 1:
actions.append(1)
if x in pots:
pots[x] += 1
else:
pots[x] = 1
k_min = min(k_min, max(pots.values()))
elif t == 2 and x in pots and pots[x] > 0:
pots[x] -= 1
actions.append(0)
else:
print(-1)
break
else:
print(k_min)
print(*actions)
```		 [{"input": "13\n1 2\n1 3\n1 1\n1 3\n1 2\n2 3\n1 3\n1 3\n2 3\n1 3\n2 2\n2 3\n2 1\n", "output": "3\n1 1 1 0 0 1 0 1\n", "testtype": "stdin"}, {"input": "4\n2 3\n1 4\n2 1\n1 2\n", "output": "-1\n", "testtype": "stdin"}, {"input": "30\n1 25\n1 2\n1 10\n1 18\n2 18\n1 11\n2 11\n1 21\n1 6\n2 2\n2 10\n1 11\n1 24\n1 11\n1 3\n1 2\n1 18\n2 25\n1 8\n1 10\n1 11\n2 18\n2 10\n1 10\n2 2\n1 24\n1 10\n2 10\n1 25\n2 6\n", "output": "4\n1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE
import sys
import threading
def main():
import sys
import math
sys.setrecursionlimit(1 << 25)
N = int(sys.stdin.readline())
events = []
potion_indices = {}
monster_indices = {}
t_list = []
x_list = []
pick_up_indices = []
action_indices = []
for idx in range(N):
t_i, x_i = sys.stdin.readline().split()
t_i = int(t_i)
x_i = int(x_i)
events.append((t_i, x_i))
t_list.append(t_i)
x_list.append(x_i)
if t_i == 1:
if x_i not in potion_indices:
potion_indices[x_i] = []
potion_indices[x_i].append(idx)
pick_up_indices.append(idx)
elif t_i ==2:
if x_i not in monster_indices:
monster_indices[x_i] = []
monster_indices[x_i].append(idx)
action = [0]*len(pick_up_indices)
possible = True
max_potions = 0
from collections import deque, defaultdict
carry = defaultdict(int)
total_potions = 0
K = 0
# For each type x, match potions to monsters
for x in monster_indices:
if x not in potion_indices or len(potion_indices[x]) < len(monster_indices[x]):
print(-1)
return
potions = potion_indices[x]
monsters = monster_indices[x]
i = len(potions)-1
j = len(monsters)-1
while j>=0:
while i>=0 and potions[i]>=monsters[j]:
i-=1
if i<0:
print(-1)
return
# Assign potion at potions[i] to monster at monsters[j]
pickup_idx = potions[i]
action_idx = pick_up_indices.index(pickup_idx)
action[action_idx]=1
i-=1
j-=1
# For remaining potions, we can choose not to pick them up
# Now simulate events to compute K
carry = defaultdict(int)
total_potions = 0
K = 0
action_ptr = 0
for idx in range(N):
t_i, x_i = events[idx]
if t_i == 1:
if action[action_ptr]:
carry[x_i] +=1
total_potions +=1
if total_potions > K:
K = total_potions
action_ptr +=1
elif t_i == 2:
if carry[x_i]>0:
carry[x_i]-=1
total_potions -=1
else:
# Should not happen as per assignment
print(-1)
return
print(K)
print(' '.join(map(str, action)))
threading.Thread(target=main).start()
```		 [{"input": "13\n1 2\n1 3\n1 1\n1 3\n1 2\n2 3\n1 3\n1 3\n2 3\n1 3\n2 2\n2 3\n2 1\n", "output": "3\n1 1 1 0 0 1 0 1\n", "testtype": "stdin"}, {"input": "4\n2 3\n1 4\n2 1\n1 2\n", "output": "-1\n", "testtype": "stdin"}, {"input": "30\n1 25\n1 2\n1 10\n1 18\n2 18\n1 11\n2 11\n1 21\n1 6\n2 2\n2 10\n1 11\n1 24\n1 11\n1 3\n1 2\n1 18\n2 25\n1 8\n1 10\n1 11\n2 18\n2 10\n1 10\n2 2\n1 24\n1 10\n2 10\n1 25\n2 6\n", "output": "4\n1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0\n", "testtype": "stdin"}]
kimi ```python
import sys
input = sys.stdin.readline
from heapq import heappush, heappop

def main():
N = int(input())
TX = [tuple(map(int, input().split())) for _ in range(N)]
potion = [0] * (N + 1)
used_potion = [0] * (N + 1)
event = [[] for _ in range(N + 1)]
for i in range(N):
(t, x) = TX[i]
t = t - 1
x = x - 1
event[x].append(i)
if t == 0:
potion[x] += 1
M = 0
q = []
for x in range(N + 1):
if potion[x] == 0 and event[x]:
print(-1)
return
M = max(M, potion[x])
for _ in range(potion[x]):
heappush(q, (-potion[x], x))

ans = [0] * N
for i in range(N - 1, -1, -1):
(t, x) = TX[i]
t = t - 1
x = x - 1
if t == 0:
if not event[x]:
continue
idx = event[x].pop()
used_potion[x] += 1
M -= 1
ans[idx] = 1
continue
if used_potion[x] == potion[x]:
if not q:
print(-1)
return
(p, y) = heappop(q)
p = -p
if p > potion[y]:
heappush(q, (-(p - 1), y))
potion[y] -= 1
M -= 1
ans[i] = 1
else:
used_potion[x] += 1
M += 1
ans[i] = 1
print(M)
print(*ans)
main()
```		 [{"input": "13\n1 2\n1 3\n1 1\n1 3\n1 2\n2 3\n1 3\n1 3\n2 3\n1 3\n2 2\n2 3\n2 1\n", "output": "3\n1 1 1 0 0 1 0 1\n", "testtype": "stdin"}, {"input": "4\n2 3\n1 4\n2 1\n1 2\n", "output": "-1\n", "testtype": "stdin"}, {"input": "30\n1 25\n1 2\n1 10\n1 18\n2 18\n1 11\n2 11\n1 21\n1 6\n2 2\n2 10\n1 11\n1 24\n1 11\n1 3\n1 2\n1 18\n2 25\n1 8\n1 10\n1 11\n2 18\n2 10\n1 10\n2 2\n1 24\n1 10\n2 10\n1 25\n2 6\n", "output": "4\n1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0\n", "testtype": "stdin"}]
minimax ```python
# YOUR CODE HERE
from collections import defaultdict

def can_defeat_all_monsters(events):
# Initialize variables
potions = defaultdict(int)
max_potions = 0
min_k = float('inf')
actions = []

# Process events
for event in events:
t, x = event
if t == 1:
# Pick up potion
potions[x] += 1
max_potions = max(max_potions, sum(potions.values()))
actions.append(1)
else:
# Encounter monster
if potions[x] > 0:
potions[x] -= 1
else:
# Cannot defeat monster
return -1, []

# Check if it's possible to defeat all monsters
if max_potions < len(events):
return -1, []

# Find the minimum K_min
for k in range(max_potions, 0, -1):
if all(sum(potions.values()) >= len(events) - i for i, (t, x) in enumerate(events) if t == 2):
min_k = k
break

return min_k, actions

# Read		 [{"input": "13\n1 2\n1 3\n1 1\n1 3\n1 2\n2 3\n1 3\n1 3\n2 3\n1 3\n2 2\n2 3\n2 1\n", "output": "3\n1 1 1 0 0 1 0 1\n", "testtype": "stdin"}, {"input": "4\n2 3\n1 4\n2 1\n1 2\n", "output": "-1\n", "testtype": "stdin"}, {"input": "30\n1 25\n1 2\n1 10\n1 18\n2 18\n1 11\n2 11\n1 21\n1 6\n2 2\n2 10\n1 11\n1 24\n1 11\n1 3\n1 2\n1 18\n2 25\n1 8\n1 10\n1 11\n2 18\n2 10\n1 10\n2 2\n1 24\n1 10\n2 10\n1 25\n2 6\n", "output": "4\n1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0\n", "testtype": "stdin"}]
wenxinyiyan ```python
from collections import defaultdict

def can_defeat_monsters(events):
# Dictionary to keep track of potions found and used
potions = defaultdict(int)
# List to record actions (picking up potions or not)
actions = []
# Variable to keep track of the maximum number of potions at any point
max_potions = 0

# Iterate through the events
for t, x in events:
if t == 1: # Finding a potion
# Always pick up the potion, but record the action as 0 initially
potions[x] += 1
actions.append(0)
# Update the maximum number of potions if necessary
max_potions = max(max_potions, sum(potions.values()))
else: # Encountering a monster
if potions[x] == 0: # No potion to defeat the monster
return -1
# Use a potion to defeat the monster
potions[x] -= 1
# Check if the last potion of this type was used
if potions[x] == 0 and actions[-1] == 0:
# If so, backtrack to the last potion found of this type and change the action to 1
for i in range(len(actions) - 1, -1, -1):
if actions[i] == 0:
actions[i] = 1
break

# Go through the actions list again and minimize the number of potions picked up
current_potions = 0
for i in range(len(actions)):
if actions[i] == 0: # Currently not picking up this potion
# Check if picking up this potion would exceed the maximum number of potions
if current_potions + potions[events[i][1]] + 1 > max_potions:
actions[i] = 1 # Change the action to picking up the potion
current_potions += 1
else:
# Not picking up the potion, but adjust the current number of potions accordingly
current_potions += potions[events[i][1]]
else:
current_potions += 1

# Return the minimum number of potions and the actions
return max_potions, ' '.join(map(str, actions))

# Read the input from stdin
N = int(input())
events = [tuple(map(int, input().split())) for _ in range(N)]

# Solve the problem and write the answer to stdout
result = can_defeat_monsters(events)
if result == -1:
print(-1)
else:
print(result[0])
print(result[1])
```		 [{"input": "13\n1 2\n1 3\n1 1\n1 3\n1 2\n2 3\n1 3\n1 3\n2 3\n1 3\n2 2\n2 3\n2 1\n", "output": "3\n1 1 1 0 0 1 0 1\n", "testtype": "stdin"}, {"input": "4\n2 3\n1 4\n2 1\n1 2\n", "output": "-1\n", "testtype": "stdin"}, {"input": "30\n1 25\n1 2\n1 10\n1 18\n2 18\n1 11\n2 11\n1 21\n1 6\n2 2\n2 10\n1 11\n1 24\n1 11\n1 3\n1 2\n1 18\n2 25\n1 8\n1 10\n1 11\n2 18\n2 10\n1 10\n2 2\n1 24\n1 10\n2 10\n1 25\n2 6\n", "output": "4\n1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0\n", "testtype": "stdin"}]
zhipu ```python
import sys
input = sys.stdin.read

def main():
data = input().split()
n = int(data[0])
events = [(int(data[i*2+1]), int(data[i*2+2])) for i in range(n)]

# To store the number of potions of each type
potions = [0] * (n + 1)
# To store the actions taken for each potion event
actions = []
# To track the maximum number of potions at any point
max_potions = 0
# To track the minimum number of potions needed to not be defeated
min_needed = 0

# First pass: determine if it's possible to defeat all monsters
for t, x in events:
if t == 1:
potions[x] += 1
elif t == 2:
if potions[x] == 0:
print(-1)
return
potions[x] -= 1

# Reset potions count for second pass
potions = [0] * (n + 1)

# Second pass: determine the minimum K_min
for t, x in events:
if t == 1:
actions.append(0) # Default to not picking up
if potions[x] < min_needed:
actions[-1] = 1 # Pick up if needed to ensure we can defeat future monsters
potions[x] += 1
elif t == 2:
potions[x] -= 1
# After using a potion, check if we need more potions in the future
min_needed = max(min_needed, potions[x] + 1)

# Calculate the maximum number of potions at any point
current_potions = 0
for i, (t, x) in enumerate(events):
if t == 1:
if actions[i] == 1:
current_potions += 1
max_potions = max(max_potions, current_potions)
elif t == 2:
current_potions -= 1

print(max_potions)
print(' '.join(map(str, actions)))

if __name__ == "__main__":
main()
```		 [{"input": "13\n1 2\n1 3\n1 1\n1 3\n1 2\n2 3\n1 3\n1 3\n2 3\n1 3\n2 2\n2 3\n2 1\n", "output": "3\n1 1 1 0 0 1 0 1\n", "testtype": "stdin"}, {"input": "4\n2 3\n1 4\n2 1\n1 2\n", "output": "-1\n", "testtype": "stdin"}, {"input": "30\n1 25\n1 2\n1 10\n1 18\n2 18\n1 11\n2 11\n1 21\n1 6\n2 2\n2 10\n1 11\n1 24\n1 11\n1 3\n1 2\n1 18\n2 25\n1 8\n1 10\n1 11\n2 18\n2 10\n1 10\n2 2\n1 24\n1 10\n2 10\n1 25\n2 6\n", "output": "4\n1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0\n", "testtype": "stdin"}]
deepseek-v3 ```python
# YOUR CODE HERE
def main():
import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
events = []
idx = 1
for _ in range(N):
t = int(data[idx])
x = int(data[idx+1])
events.append((t, x))
idx += 2

# To track the potions we need to pick up
# We will count the number of monsters for each type
monster_counts = {}
for t, x in events:
if t == 2:
monster_counts[x] = monster_counts.get(x, 0) + 1

# Now, we need to ensure that for each monster type, we have at least as many potions as monsters
# We will keep track of the potions we have
potions = {}
actions = []
max_potions = 0
# We will process the events in reverse order to determine which potions to pick up
# This way, we can ensure that we have enough potions for the monsters
# We will use a stack to keep track of the potions we need to pick up
stack = []
for t, x in reversed(events):
if t == 2:
stack.append(x)
else:
if stack and stack[-1] == x:
stack.pop()
actions.append(1)
potions[x] = potions.get(x, 0) + 1
max_potions = max(max_potions, sum(potions.values()))
else:
actions.append(0)

# Now, check if all monsters have been accounted for
for x in monster_counts:
if potions.get(x, 0) < monster_counts[x]:
print(-1)
return

# Now, we need to find the minimal K_min
# To do this, we need to find the minimal maximum number of potions at any time
# We can achieve this by picking up the potions as late as possible
# So, we will iterate through the events in order and pick up the potions only when necessary
# We will also keep track of the current number of potions
current_potions = {}
actions_final = []
max_potions_final = 0
for t, x in events:
if t == 1:
if x in monster_counts and monster_counts[x] > current_potions.get(x, 0):
actions_final.append(1)
current_potions[x] = current_potions.get(x, 0) + 1
max_potions_final = max(max_potions_final, sum(current_potions.values()))
else:
actions_final.append(0)
else:
if x in current_potions and current_potions[x] > 0:
current_potions[x] -= 1
max_potions_final = max(max_potions_final, sum(current_potions.values()))

# Now, we have the minimal K_min
# We need to collect the actions for the potion events
potion_actions = []
for i in range(N):
if events[i][0] == 1:
potion_actions.append(actions_final[i])

print(max_potions_final)
print(' '.join(map(str, potion_actions)))

if __name__ == "__main__":
main()
```		 [{"input": "13\n1 2\n1 3\n1 1\n1 3\n1 2\n2 3\n1 3\n1 3\n2 3\n1 3\n2 2\n2 3\n2 1\n", "output": "3\n1 1 1 0 0 1 0 1\n", "testtype": "stdin"}, {"input": "4\n2 3\n1 4\n2 1\n1 2\n", "output": "-1\n", "testtype": "stdin"}, {"input": "30\n1 25\n1 2\n1 10\n1 18\n2 18\n1 11\n2 11\n1 21\n1 6\n2 2\n2 10\n1 11\n1 24\n1 11\n1 3\n1 2\n1 18\n2 25\n1 8\n1 10\n1 11\n2 18\n2 10\n1 10\n2 2\n1 24\n1 10\n2 10\n1 25\n2 6\n", "output": "4\n1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0\n", "testtype": "stdin"}]