Alchemy 질문있습니다ㅜㅜ

  • swg0110
    swg0110

    i번째 물질의 재료 set의 sub set으로 만들 수 있는 물질들이 있을 때, 그 물질들의 재료 set들의 intersection 이 empty set이면 IMPOSIBLE한 것이고, 아닐 경우 그 intersection에 속하는 임의의 원소를 마지막으로 보내는 식으로 reordering을 했는데요.. 계속 오답이 뜨네요... 제가 고려하지 못한 부분이 무엇이 있을까요?
    답변해주시면 정말 감사하겠습니다. 감사합니다ㅠㅠ
    (아 그리고 재료의 개수가 같고 물질의 index가 더 큰 경우도 고려했습니다..)

    #include <iostream>
#include <list>
#include <string.h>

#define NOANSWER    -999
#define UNDEFINED   -1

using namespace std;

int matCnt;
list<int>* material;
list<int>* conMat;
int* lastMat;

int findLastMat(int idx);

int main() {
    int tc, ti = 0;

    cin >> tc;

    while (ti < tc) {
        cin >> matCnt;

        material = new list<int>[matCnt];
        conMat = new list<int>[matCnt];

        for (int i = 0; i < matCnt; i++) {
            int cmc = 0;
            cin >> cmc;

            for (int j = 0; j < cmc; j++) {
                int matIdx = 0;
                cin >> matIdx;
                matIdx -= 1;
                material[i].push_back(matIdx);
                conMat[matIdx].push_back(i);
            }
        }

        lastMat = new int[matCnt];

        for (int i = 0; i < matCnt; i++) {
            lastMat[i] = findLastMat(i);
        }

        for (int i = 0; i < matCnt; i++) {
            if (lastMat[i] == NOANSWER) {
                cout << "IMPOSIBLE" << endl;
                continue;
            }

            cout << (int)material[i].size();

            list<int>::iterator it = material[i].begin();
            list<int>::iterator end = material[i].end();

            int lastIdx = lastMat[i];
            while (it != end) {
                int matIdx = (*it);

                if ((lastIdx != UNDEFINED) &&
                    (matIdx == lastIdx)) {
                    it++;
                    continue;
                }

                cout << ' ' << (matIdx + 1);

                it++;
            }

            if (lastIdx != UNDEFINED)
                cout << ' ' << (lastIdx + 1);

            cout << endl;
        }

        if (ti < (tc - 1)) {
            cout << endl;
        }

        delete[] material;

        ti++;
    }
}

int findLastMat(int idx) {
    int totCnt = (int)material[idx].size();
    if (totCnt == 0) {
        return UNDEFINED;
    }

    int* conMatCnt = new int[matCnt];
    memset(conMatCnt, 0, matCnt * sizeof(int));

    list<int>::iterator it = material[idx].begin();
    list<int>::iterator end = material[idx].end();

    list<int> inclusiveMat;

    while (it != end) {
        int curIdx = (*it);
        list<int>::iterator conIt = conMat[curIdx].begin();
        list<int>::iterator conEnd = conMat[curIdx].end();

        while (conIt != conEnd) {
            int conMatIdx = (*conIt);
            if (conMatIdx == idx) {
                conIt++;
                continue;
            }

            conMatCnt[conMatIdx]++;
            conIt++;

            int curTotCnt = (int)material[conMatIdx].size();
            if (conMatCnt[conMatIdx] != curTotCnt)
                continue;

            if ((curTotCnt == totCnt) &&
                (conMatIdx > idx)) {
                delete[] conMatCnt;
                return NOANSWER;
            }

            inclusiveMat.push_back(conMatIdx);
        }

        it++;
    }

    if ((int)inclusiveMat.size() == 0) {
        delete[] conMatCnt;
        return UNDEFINED;
    }

    memset(conMatCnt, 0, matCnt * sizeof(int));

    int totConCnt = (int)inclusiveMat.size();
    list<int>::iterator inIt = inclusiveMat.begin();
    list<int>::iterator inEnd = inclusiveMat.end();

    while (inIt != inEnd) {
        int curIdx = (*inIt);

        list<int>::iterator conIt = material[curIdx].begin();
        list<int>::iterator conEnd = material[curIdx].end();

        while (conIt != conEnd) {
            int conIdx = (*conIt);
            conMatCnt[conIdx]++;

            if (conMatCnt[conIdx] == totConCnt) {
                delete[] conMatCnt;
                return conIdx;
            }

            conIt++;
        }

        inIt++;
    }

    delete[] conMatCnt;

    return NOANSWER;
}

    8년 전
0개의 댓글이 있습니다.

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.