小球投盒

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        Set<Integer> set = new HashSet<>();
        for (int i = 1; i <= n; i++) set.add(i);
        int i;
        for (i = 1; i <= m; i++) {
            if (sc.nextInt() == 1) {
                set.remove(sc.nextInt());
                if (set.isEmpty()) break;
            }
            else {
                int x = sc.nextInt();
                if (!set.contains(x)) break;
                set = new HashSet<>();
                set.add(x);
            }
        }
        System.out.println(i > m ? -1 : i);
    }
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[] a = new int[n+5];
        int[] b = new int[3];
        int[] p = new int[m+5];
        int[] x = new int[m+5];
        for (int i = 1; i <= m; i++) {
            p[i] = sc.nextInt();
            x[i] = sc.nextInt();
        }
        for (int i = 1; i <= m; i++) {
            if ((a[x[i]] & p[i]) == 0) {
                ++b[p[i]];
                a[x[i]] |= p[i];
                if (b[1] == n || b[2] == 2 || a[x[i]] == 3) {
                    System.out.print(i);
                    System.exit(0);
                }
            }
        }
        System.out.print(-1);
    }
}

import java.util.*;
import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] str = bf.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);

        Set<Integer> emptyBox = new HashSet<>();
        for(int i=1;i<=n;i++){
            emptyBox.add(i);
        }

        for(int i=0;i<m;i++){
            str = bf.readLine().split(" ");
            int op = Integer.parseInt(str[0]);
            int x = Integer.parseInt(str[1]);
            if(op==1){
                emptyBox.remove(x);
                if(emptyBox.isEmpty()){
                    System.out.println((i+1));
                    return;
                }
            }
            else{
                if(emptyBox.contains(x)){
                    emptyBox=new HashSet<>();//这里不要clear，clear会挨个遍历集合元素并移除，时间复杂度高
                    emptyBox.add(x);
                }
                else{
                    //success
                    emptyBox=new HashSet<>();
                    System.out.println((i+1));
                    return;
                }
            }
        }
        System.out.println(-1);
    }
}

用上面大佬的思路写了个BitSet版本的。
其实这题的数据不大，BitSet没有必要。

import java.util.BitSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        BitSet bit1 = new BitSet(n);//至少有一个小球的盒子的集合
        int res = 0;
        for (int i = 0; i < m; i++) {
            res++;
            int t = in.nextInt();
            int b = in.nextInt();
            BitSet bit2 = new BitSet(n);
            if (t == 1) {
                //如果是1，就把bit1的第b位设置为true
                bit1.set(b - 1);
            } else {
                //如果是2，就把bit2的第b位设置为true
                //稍后取反
                bit2.set(b - 1);
            }
            
            //如果bit2不为0，说明有一个第二种操作，除了bit2中的那一个盒子，别的盒子至少都被放了一个小球
            //将bit2取反后就是所有至少有一个小球的盒子，用与操作更新到bit1中。
            if (bit2.cardinality() != 0 ) {
                bit2.flip(0, n);
                bit1.or(bit2);
            }
            if (bit1.cardinality() == n) {
                break;
            }
        }
        System.out.println(bit1.cardinality() == n ? res : -1);
    }
}

傻子用二分做的

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

def canSatisfied(mid: int):
    diff = [0] * (n + 1)
    type1 = set()
    for t, x in ord[:mid]:
        x -= 1
        if t == 1:
            type1.add(x)
        else:
            diff[0] += 1
            diff[x] -= 1
            diff[x + 1] += 1
            diff[n] -= 1
    acc = 0
    for i in range(n):
        acc = acc + diff[i]
        if acc == 0 and i not in type1:
            return False
    return True


l, r = 1, m
while l < r:
    mid = (l + r) // 2
    if canSatisfied(mid):
        r = mid
    else:
        l = mid + 1
if canSatisfied(l):
    print(l)
else:
    print(-1)