글 읽기 - 메모리 초과...

gunwookim 4년 전 0

흐음...
메모리 초과가 뜰 수가 없을거 같은데 왜 뜰까요?

제 생각엔 2가지 인거 같아요.

queue 넘침 (이게 제일 유력함)
벡터 ans 에 많은 값 저장

고수분들 도와주세요 ㅠㅠ

#include <bits/stdc++.h>
using namespace std;
int n;
int nx[6] = {-5,-1,4,-4,1,5}; /// 앞 3개 : 왼쪽 뒤 3개 : 오른쪽
int ny[6] = {-1,0,1,-1,0,1};
int c[25005];
int p[25005];
pair <int,int> a[25005];

bool Check(int x,int line,int What_line)
{
    if(x < 0||x > n*n-n/2) return false;
    if(c[x]) return true;
    if(What_line&&(x-1) % (2*n-1) == 0) return true;
    if(!What_line&&(x-n-1) % (2*n-1) == 0) return true;
    return false;
}

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n*n-n/2;i++)
    {
        scanf("%d %d", &a[i].first, &a[i].second);
    }
    queue < pair <int,int> > q;
    q.push({1,1});
    p[1] = -1;
    c[1] = 1;
    int now,cost,line,dx;
    while(!q.empty())
    {
        now = q.front().first;
        cost = q.front().second;
        q.pop();
        if(now == n*n-n/2) continue;
        line = 2*((now-1)/(2*n-1)) + ((now-1)%(2*n-1))/n+1;
        cout << now << " " << cost << " " << line << "\n";
        for(int i = 0;i < 3;i++)
        {
            dx = now+nx[i];
            if(Check(dx,line+ny[i],line % 2)) continue;
            if(a[dx].second != a[now].first) continue;
            p[dx] = now;
            c[dx] = cost+1;
            q.push({dx,cost+1});
        }
        for(int i = 3;i < 6;i++)
        {
            dx = now+nx[i];
            if(Check(dx,line+ny[i],line % 2)) continue;
            if(a[dx].first != a[now].second) continue;
            p[dx] = now;
            c[dx] = cost+1;
            q.push({dx,cost+1});
        }
    }
    vector <int> ans;
    for(int i = n*n-n/2;i >= 1;i--)
    {
        if(c[cost] != 0)
        {
            for(int j = i;j != -1;j = p[j])
            {
                ans.push_back(j);
            }
            printf("%d\n",c[i]);
            break;
        }
    }
    reverse(ans.begin(),ans.end());
    for(auto x : ans)
    {
        printf("%d ",x);
    }
}

morpheus 1년 전 0

pair형 배열을 쓰면 메모리초과가 뜨더라구요..

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

문제

문제

출처

ICPC

메모리 초과...

gunwookim 4년 전 0

morpheus 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말