알고스팟 9주년 대회 D번 Spotboard 질문입니다.

  • fanatic100
    fanatic100

    SPOTBOARD
    많이 시도를 해봤는데 어느부분에서 틀렸는지 찾기가 힘듭니다.

    FREEZE 이전에는 tarr에 제출들을 반영 하고
    FREEZE 이후에는 tarr2에 tarr을 복사한뒤
    tarr2에 제출들을 반영하였습니다.
    모든 제출을 받은 뒤에는 둘을 비교해가며 답을 하나씩 체크하고 순위를 스왑해가며 변동시키는 방식입니다. 어느부분이 틀렸는지 계속 오답이 뜹니다. 도와주세요!

    #include <iostream>
    #include <iostream>
    #include <tuple>
    #include <algorithm>
    #include <string.h>
    #include <vector>
    #include <set>
    using namespace std;
    
    int N, M, K, F;
    struct Team {
        int timeP;
        int ty[22];
        int ctime[22];
        int teamNum;
        int correct;
        int isCorrect;
        int lastCorrect;
        int lastCheck;
        void acProb(int T, int p) {
            timeP += T + ty[p] * 20;
            isCorrect ^= 1 << p;
            correct++;
            ctime[p] = T;
            lastCorrect = max(lastCorrect, T);
        }
        void acProb(int T, int p, int tryNum) {
            timeP += T + tryNum * 20;
            isCorrect ^= 1 << p;
            correct++;
            ctime[p] = T;
            lastCorrect = max(lastCorrect, T);
        }
        //맞은 문제인가?
        bool checkProb(int idx) {
            return (isCorrect & (1 << idx)) != 0;
        }
        void init(int idx) {
            teamNum = idx;
            timeP = 0;
            memset(ty, 0, sizeof(ty));
            memset(ctime, 0, sizeof(ctime));
            correct = 0;
            lastCorrect = 0;
            lastCheck = 0;
            isCorrect = 0;
        }
        void copy(Team* b) {
            timeP = b->timeP;
            memcpy(ctime, b->ctime, sizeof(ctime));
            memcpy(ty, b->ty, sizeof(ty));
            teamNum = b->teamNum;
            correct = b->correct;
            isCorrect = b->isCorrect;
            lastCorrect = b->lastCorrect;
            lastCheck = b->lastCheck;
        }
    };
    
    bool same(Team *a, Team *b) {
        if ((a->correct == b->correct) &&
            (a->timeP == b->timeP) &&
            (a->lastCorrect == b->lastCorrect))
            return true;
        else
            return false;
    }
    
    bool cmp(Team *a, Team *b) {
        if (a->correct == b->correct) {
            if (a->timeP == b->timeP) {
                if (a->lastCorrect == b->lastCorrect)
                    return a->teamNum < b->teamNum;
                return a->lastCorrect < b->lastCorrect;
            }
            return a->timeP < b->timeP;
        }
        return a->correct > b->correct;
    }
    
    Team* tarr[510];
    Team* tarr2[510];
    int main() {
    
        cin >> N >> M >> K >> F;
        int T, t, p, r;
        for (int i = 0; i <= N; i++) {
            tarr[i] = new Team();
            tarr2[i] = new Team();
            tarr[i]->init(i);
            tarr2[i]->init(i);
        }
        int i = 0;
        //freeze 이전처리
        for (; i < K; i++) {
            cin >> T >> t >> p >> r;
            if (T >= F)
                break;
            if (!tarr[t]->checkProb(p)) {
                if (r)
                    tarr[t]->acProb(T, p);
                else
                    tarr[t]->ty[p]++;
            }
        }
        //복사
        for (int xx = 1; xx <= N; xx++) {
            tarr2[xx]->copy(tarr[xx]);
        }
        //freeze 이후처리
        for (; i < K; i++) {
            if (!tarr2[t]->checkProb(p)) {
                if (r)
                    tarr2[t]->acProb(T, p);
                else
                    tarr2[t]->ty[p]++;
            }
            if ((i + 1)<K)
                cin >> T >> t >> p >> r;
        }
    
        int lastIdx = N;
        sort(tarr + 1, tarr + N + 1, cmp);
        vector<tuple<int, int, int>> ans;
        while (lastIdx>0) {
            Team* beforeTeam = tarr[lastIdx];
            Team* afterTeam = tarr2[tarr[lastIdx]->teamNum];
            //모두 확인했는지 체크
            if (same(beforeTeam, afterTeam)) {
                lastIdx--;
            }
            else {
                int myIdx = beforeTeam->teamNum;
                int brank = 1;
                //이전순위체크
                for (int i = lastIdx; i >= 2; i--) {
                    if (!same(tarr[i - 1], tarr[i])) {
                        brank = i;
                        break;
                    }
                }
                int now = beforeTeam->lastCheck + 1;
                //나중에 맞춘문제 찾기
                while (!(!beforeTeam->checkProb(now) && afterTeam->checkProb(now)))
                    now++;
                //cout << now << endl;
                beforeTeam->acProb(afterTeam->ctime[now], now, afterTeam->ty[now]);
    
                //재정렬
                int idx2 = lastIdx;
                for (; idx2 >= 2; idx2--) {
                    if (!cmp(tarr[idx2 - 1], tarr[idx2]))
                        swap(tarr[idx2 - 1], tarr[idx2]);
                    else
                        break;
                }
                //이후순위 체크
                int rank = 1;
                for (int i = idx2; i >= 2; i--) {
                    if (!same(tarr[i - 1], tarr[i])) {
                        rank = i;
                        break;
                    }
                }
                ans.push_back(make_tuple(myIdx, brank, rank));
            }
        }
        int a, b, c;
        cout << ans.size() << endl;
        for (int i = 0; i < ans.size(); i++) {
            tie(a, b, c) = ans[i];
            cout << a << " " << b << " " << c << endl;
        }
        return 0;
    }
    


    7년 전
14개의 댓글이 있습니다.
  • hyunhwan
    hyunhwan

    정확하게 확인 해본 것은 아닙니다만, 마지막 순위 체크하는 부분에서

            //모두 확인했는지 체크
            if (same(beforeTeam, afterTeam)) {
                lastIdx--;
            }
    

    same함수의 경우 동일한 팀을 처리하였는지를 확인하려고 사용을 하셨을 것 같은데, 제가 생각한게 맞다면 이 경우에 다른 팀을 같은 팀으로 간주하여 잘못 처리 되지 않을까 싶네요.


    7년 전 link
  • fanatic100
    fanatic100

    답변 감사합니다! 저부분의 경우 beforeTeam의 teamNum을 통헤 afterTeam을 찾은 뒤에 둘을 비교하기 때문에 같은팀이 맞는것 같습니다


    7년 전 link
  • hyunhwan
    hyunhwan

    아마 제가 했던 실수랑 비슷한 실수를 하신거 같다는 생각이 듭니다.

    한 팀이 같은 시간에 같은 문제를 여러번 제출하는 경우나, 여러팀이 동시에 같은 시간(t)에 제출하는 경우도 잘 처리가 되나요?
    참고로 문제에서 다음과 같은 조건이 있습니다.

    • Total time이 같은 경우 마지막으로 푼 문제를 먼저 푼 팀이 등수가 높다.

    이에 대해서는 실제로 시간만 고려하는 것이 아니라 제출 순서 역시 고려를 해야하는 것으로 알고 있습니다.


    7년 전 link
  • fanatic100
    fanatic100

    그렇다면 동점자는 어떻게 나오게 되는건가요?
    마지막 제출이 시간이 아니라 순서에 의해 결정되는것이면
    아에 풀지 않은것을 제외하면 동점이 나올 수 없을것같은데요
    문제의 Example2에 팀1과 팀2가 freeze 이전엔 동점으로 나오기 떄문에 팀2가 공동 1등으로 나오는데 팀 2가 나중에 제출했으니
    2 1 1이 아닌 2 2 1이 되어야 하는것 아닌가요?


    7년 전 link
  • hyunhwan
    hyunhwan

    그 부분에 대해서는 제가 착오가 있었습니다. 뒤의 부분은 넘어가시고 찾아보시면 될것 같네요.


    7년 전 link
  • fanatic100
    fanatic100

    잘모르겠어요... 답안 공개시에 정답이 나오면 제대로 마지막으로 제출된 시간도 갱신이 되는데말이죠...


    7년 전 link
  • hyunhwan
    hyunhwan

    다시금 뜯어봐도 문제가 있는부분이 잘 보이지 않아서 데이터를 뜯어봤더니 뭔가 문제가 있어서 재채점중이고, 세번째 제출에 정답을 받으신걸로 확인합니다. 저도 좀더 깊게 확인해봐야했는데 시간을 허비하게 해드린거 같아서 대단히 죄송하게 생각합니다.


    7년 전 link
  • fanatic100
    fanatic100

    해결이 되서 다행이네요! 신경써주셔서 감사합니다.


    7년 전 link
  • jwvg0425
    jwvg0425

    혹시 여기 코드에서 뭔가 잘못된 부분(고려하지 못한 부분)이 있나요? 저도 계속 제출해서 실패 실패하는데 랜덤 인풋 생성해서 이 코드랑 답 비교해보면 항상 같은 답안이 나오네요.


    7년 전 link
  • fanatic100
    fanatic100

    일단 정답받은겁니다.


    7년 전 link
  • hyunhwan
    hyunhwan

    @jwvg0425 // 소스코드를 봤는데, 제출 기록을 정렬할 때 시간만 고려해서 정렬이 되는 것 같습니다. 이 경우에는 한팀이 같은 시간에 여러번 제출 했을 때에 순서가 제대로 유지 되지 않을텐데요. 이 부분을 고려해서 작성해보심이 어떨까요?


    7년 전 link
  • jwvg0425
    jwvg0425

    으어.. 정렬을 안 하니까 통과가 되네요. 답변 감사합니다. 저는 문제 조건에서 제출 기록이 반드시 시간 순서대로(제출 순서대로) 들어온다는 조건이 없어서 시간 순으로 정렬해야한다고 생각했는데 입력 자체가 항상 정렬된 순서대로 들어오네요. Input에 이걸 좀 더 명확히 적어주시면 어떨까요? ㅜㅜ


    7년 전 link
  • hyunhwan
    hyunhwan

    문제에 명시 되어 있습니다.

    두 번째 줄부터 K개의 줄에 걸쳐 각 줄에 하나씩 답안의 정보들이 제출 순서대로 주어진다.


    7년 전 link
  • jwvg0425
    jwvg0425

    헉;; 그렇군요. 왜 못 봤을까요 ㅠㅜ 괜히 한참 뻘짓했네요. 문제를 좀 더 꼼꼼히 보는 습관을 들여야겠습니다.. 감사합니다.


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