글 읽기 - 시간 초과

dontsaymyid 2년 전 0

제시된 예제도 모두 빠르고 정확하게 풀었고, N = 1024인 케이스도 별 무리 없이 해결한 이 코드가 7%에서 시간 초과가 났습니다. 특정한 테스트 케이스에 대해 무한루프에 빠지는 경우가 생기는 것 같습니다.. 고수 분들의 힌트 부탁드립니다.

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

class primes
{
private:
    vector<int> prime { 2, 3, 5, 7 };
    int size = 4;

public:
// 에라토스테네스의 체를 이용하여 max 이하의 모든 소수를 구하는 생성자.
// 구한 소수는 prime 벡터에 저장한다.
    primes(int max)
    {
        int sq = 9;
        bool isprime;
        for (int c = 2; sq < max; c++)
        {
            sq = prime[c] * prime[c];
            for (int n = prime[c - 1] * prime[c - 1] + 2; n < sq; n++)
            {
                isprime = true;
                for (int i = 0; i < c; i++)
                    if (n % prime[i] == 0)
                    {
                        isprime = false;
                        break;
                    }
                if (isprime)
                {
                    prime.push_back(n);
                    size++;
                }
            }
        }
    }
    
// 이분 검색을 이용하여 _x가 max 이하의 소수인지 판단하는 함수.
    bool search(int _x)
    {
        int left = 0;
        int right = size - 1;
        int mid;
        while (left <= right)
        {
            mid = (left + right) / 2;
            if (_x < prime[mid])
                right = mid - 1;
            else if (_x > prime[mid])
                left = mid + 1;
            else
                return true;
        }
        return false;
    }
};

int main()
{
    int n;
    cin >> n;
    vector<int> input(n, 0);
    int max = 0;
    for (int &x : input)
    {
        cin >> x;
        if (max < x)
            max = x;
    }
    primes p(max * 2);
// 입력된 수를 가지고 정점을 만들 때, 에지를 저장하는 인접 리스트.
    vector<vector<int>> adjlist(n, vector<int>());
// primes::search() 함수를 이용해 합이 소수인 정점을 무방향 에지로 연결한다.
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (p.search(input[i] + input[j]))
            {
                adjlist[i].push_back(j);
                adjlist[j].push_back(i);
            }
// 주어진 그래프는 항상 이분 그래프가 맞다. (수학적인 증명은 생략)
// 아래 코드는 DFS를 이용해 실제로 정점을 이분하는 과정으로,
// perfect matching을 위해 이분된 집합의 원소의 개수를 직접 센다.
    vector<bool> visited(n, false);
    vector<bool> color(n, false);
    stack<int> remain;
    int current;
    int u, v;
    for (int i = 0; i < n; i++)
    {
        if (visited[i])
            continue;
        visited[i] = true;
        remain.push(i);
        u = 1, v = 0;
        while (!remain.empty())
        {
            current = remain.top();
            remain.pop();
            for (auto j : adjlist[current])
                if (!visited[j])
                {
                    visited[j] = true;
                    remain.push(j);
                    u += color[current];
                    v += color[j] = !color[current];
                }
        }
        if (u != v)
        {
            cout << -1;
            return 0;
        }
    }
// 분할된 집합을 renumbering하는 과정.
// 첫 번째 원소가 포함된 집합을 U, 여집합을 V라 할 때,
// left와 right는 각각 U와 V의 원소가 몇 번째 입력값인지 저장한다.
    vector<int> left, right;
    for (int i = 0; i < n; i++)
        (color[i] ? right : left).push_back(i);
// 입력받은 수가 V의 몇 번째 원소인지 저장하는 벡터. U의 원소는 -1로 표기한다.
    vector<int> invright(n, -1);
    n /= 2;
    for (int i = 0; i < n; i++)
        invright[right[i]] = i;
// adjlist를 left와 right 벡터에 맞게 renumbering한 인접 리스트.
// adjlist에서 시작점이 U의 원소인 에지만 저장하며,
// 각 에지가 U의 몇 번째 원소에서 V의 몇 번째 원소로 향하는지 저장한다.
    vector<vector<int>> modadjlist(n, vector<int>());
    for (int i = 0; i < n; i++)
    {
        modadjlist[i] = adjlist[left[i]];
        for (int &j : modadjlist[i])
            j = invright[j];
    }
// 이분 매칭
    vector<int> lmatch(n, -1);
    vector<bool> rmatch(n, false);
    vector<int> res;
    u = 0;
    lmatch[0] = 0;
    rmatch[modadjlist[0][0]] = true;
    while (u >= 0)
    {
        if (u == n - 1)
        {
            res.push_back(input[right[modadjlist[0][lmatch[0]]]]);
            for (int i = 1; i < n; i++)
                lmatch[i] = -1;
            for (int i = 0; i < n; i++)
                rmatch[i] = false;
            if (++lmatch[0] == modadjlist[0].size())
                break;
            rmatch[modadjlist[0][lmatch[0]]] = true;
            u = 0;
            continue;
        }
        else if (lmatch[u] == modadjlist[u].size())
        {
            lmatch[u] = -1;
            u--;
        }
        else
            u++;
        if (lmatch[u] < modadjlist[u].size())
            rmatch[modadjlist[u][lmatch[u]]] = false;
        while (++lmatch[u] < modadjlist[u].size())
            if (!rmatch[modadjlist[u][lmatch[u]]])
            {
                rmatch[modadjlist[u][lmatch[u]]] = true;
                break;
            }
    }
    if (res.empty())
        cout << -1;
    else
    {
        sort(res.begin(), res.end());
        for (int i : res)
            cout << i << ' ';
    }
    return 0;
}

dontsaymyid 2년 전 0

N = 50짜리 테스트를 랜덤으로 생성해보니까 바로 반례가 나오네요. 30초가 지나도 안 끝나는 케이스입니다.

[Input]
50
 7 606 761 464
372 551 668 889
353 916 611 868
332 599 644  59
469 844 967 630
950 909 708 295
711 962 259 786
480 213 670 895
411 932 543 120
164 145 352 725

[Output]
TLE

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 초과

dontsaymyid 2년 전 0

dontsaymyid 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말