[PAT-A] 1169 The Judger

Java

测试点5超时

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int t1 = Integer.parseInt(st.nextToken());
        int t2 = Integer.parseInt(st.nextToken());
        Set<Integer> set = new HashSet<>();
        set.add(t1);
        set.add(t2);

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] p = new int[n + 1][m + 1];
        boolean[] isOut = new boolean[n + 1];

        for (int i = 1; i <= n; ++i) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= m; ++j) {
                p[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int j = 1; j <= m; ++j) {
            List<Integer> out = new ArrayList<>();

            for (int i = 1; i <= n; ++i) {
                if (!isOut[i]) {
                    int x = p[i][j];
                    if (check(x, set)) {
                        set.add(x);
                    } else {
                        isOut[i] = true;
                        out.add(i);
                    }
                }
            }

            if (!out.isEmpty()) {
                Collections.sort(out);
                for (int i : out) {
                    System.out.printf("Round #%d: %d is out.\n", j, i);
                }
            }
        }

        List<Integer> win = new ArrayList<>();
        for (int i = 1; i <= n; ++i) {
            if (!isOut[i]) {
                win.add(i);
            }
        }

        if (win.isEmpty()) {
            System.out.println("No winner.");
        } else {
            Collections.sort(win);
            System.out.print("Winner(s):");
            for (int i : win) {
                System.out.print(" " + i);
            }
            System.out.println();
        }
    }

    private static boolean check(int x, Set<Integer> set) {
        if (set.contains(x)) {
            return false;
        }
        for (int it : set) {
            if (set.contains(x + it)) {
                return true;
            }
        }
        return false;
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_set>

using namespace std;

const int N = 10010;

int n, m;        // [1, n]
int p[N][N];    // p[人][轮]
bool is_out[N];
unordered_set<int> st;

bool check(int x) {
    if (st.count(x)) return false;
    for (auto it: st)
        if (st.count(x + it)) return true;

    return false;
}

int main() {
    int t1, t2;
    scanf("%d%d", &t1, &t2);
    st.insert(t1);
    st.insert(t2);

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &p[i][j]);

    for (int j = 1; j <= m; ++j) {
        vector<int> out;

        for (int i = 1; i <= n; ++i)
            if (!is_out[i]) {
                int x = p[i][j];
                if (check(x)) st.insert(x);
                else {
                    is_out[i] = true;
                    out.push_back(i);
                }
            }

        if (!out.empty()) {
            sort(out.begin(), out.end());
            for (auto i: out)
                printf("Round #%d: %d is out.\n", j, i);
        }
    }

    vector<int> win;
    for (int i = 1; i <= n; ++i)
        if (!is_out[i]) win.push_back(i);

    if (win.empty()) printf("No winner.\n");
    else {
        sort(win.begin(), win.end());

        printf("Winner(s):");
        for (auto i: win)
            printf(" %d", i);
        printf("\n");
    }
    return 0;
}