글 읽기 - C++ (deque 사용) 메모리 초과 질문드립니다.

kangrnin 4년 전 0

저는 deque에 팀으로 연결되는 학생들을 담는 방식으로 했는데,

deque에 최대 100000명이 담기더라도

int 100000개(pick), bool 100000개(team + selected), deque 다 합쳐서

256MB는 넘지 않을 것 같았지만 메모리 초과가 나네요.

어떤 부분이 원인인가요?

감사합니다.

#include <cstdio>
#include <vector>
#include <deque>
using namespace std;

int pick[100001];
bool team[100001];

int main() {
    int t, n;
    scanf("%d", &t);
    for(int i=1; i<=t; i++) {
        scanf("%d", &n);

        for(int j=1; j<=n; j++) {
            scanf("%d", &pick[j]);
            if(pick[j] == j)
                team[j] = true;
        }

        deque<int> dq;
        vector<int> selected(n+1, false);
        for(int j=1; j<=n; j++) {
            if(team[j] == true) continue;

            dq.push_back(j);
            // printf("push %d\n", j);
            selected[j] = true;

            while(1) {
                int next = pick[dq.back()];
                // printf("next = %d\n", next);
                if(team[next] == true) {
                    // printf("team broken at %d\n", next);
                    break;
                }

                if(selected[next] == true) {
                    // printf("loop found\n");
                    while(1) {
                        if(dq.front() == next) break;
                        dq.pop_front();
                    }
                    // printf("team: ");
                    while(!dq.empty()) {
                        team[dq.front()] = true;
                        // printf("%d ", dq.front());
                        dq.pop_front();
                    }
                    // printf("\n");
                    break;
                }
                dq.push_back(next);
            }
            dq.clear();
            fill(selected.begin(), selected.end(), false);
        }

        int cnt=0;
        for(int i=1; i<=n; i++)
            if(team[i] == false) cnt++;
        
        printf("%d\n", cnt);
    }
}

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

문제

문제

출처

ICPC

C++ (deque 사용) 메모리 초과 질문드립니다.

kangrnin 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말