글 읽기 - 런타임 에러가 나는 이유가 궁금합니다..

wnsgur1714 4년 전 0

Mo's algorithm으로 풀었습니다.

채점 중간에 런타임 에러가 납니다.

배열의 크기 때문에 그런 건 아닌 거 같은데.... 왜 런타임 에러가 나는지 알고 싶습니다.

#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;

struct quary{        // 쿼리들의 시작점, 도착점, 순서, 정답을 저장하는 구조체
    int s, d;        // s-시작점 d-도착점
    int number;      // 쿼리의 순서
    int value;       // 정답
};

int n, q;            // n - 문제에서의 n(배열의 크기) , q - 문제에서의 m(쿼리의 수)
int nn;              // 루트 n;
int arr[100001];     // 입력받는 수들을 저장하는 배열
quary qs/*questions*/[100001]; // 쿼리들
int nums[1000001];   // 해당 수가 다른 수인지 검사하는 배열
int value;           // 정답

bool sbma(quary a, quary b){/*sort by mo's algorithm*/  // mo's algorithm에 따라 정렬
    int c = a.d / nn;
    int d = b.d / nn;
    if(c > d){
        return false;
    }
    else if(c < d){
        return true;
    }
    else{
        if(a.s > b.s){
            return false;
        }
        else{
            return true;
        }
    }
}

bool sbnf(quary a, quary b){/*sort by number first*/    // 쿼리의 순서에 따라 정렬
    if(a.number > b.number){ 
        return false;
    }
    else{
        return true;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin >> n;
    nn = sqrt(n);                   // nn을 루트 n으로 정함 
    for(int i = 1 ; i <= n ; i++){  // 배열 입력받기 
        cin >> arr[i];
    }
    cin >> q;
    for(int i = 0 ; i < q ; i++){   // 쿼리 입력받기
        cin >> qs[i].s >> qs[i].d;
        qs[i].number = i;           // 쿼리의 순서를 나타냄
    }
    sort(qs, qs+q, sbma);           // mo's algorithm으로 정렬
    for(int i = qs[0].s ; i <= qs[0].d ; i++){  // 맨 첫번째 쿼리를 처리
        int k = nums[arr[i]]++;                 // nums에서 s 부터 d까지의 수들을++
        if(k == 0){                             // 만약 수가 저장되어 있지 않았다면 
            value++;                            // 서로 다른 수++;
        }
    }
    qs[0].value = value;                        // 쿼리에 정답을 저장
    for(int i = 1 ; i < q ; i++){            
        if(qs[i-1].s < qs[i].s){                // 이번 쿼리의 s가 전 쿼리의 s보다 클 때
            for(int j = qs[i-1].s ; j < qs[i].s ; j++){ // nums에서 전 쿼리의 s부터 이번 쿼리의 s-1까지 --(수를 없앰)
                int k = nums[arr[j]]--;
                if(k == 1){                     // 만약에 수가 num에서 없어졌다면 
                    value--;                    // 서로 다른 수--
                }
            }
        }
        else if(qs[i-1].s > qs[i].s){           // 이번 쿼리의 s가 전 쿼리의 s보다 작을 때
            for(int j = qs[i-1].s-1 ; j >= qs[i].s ; j--){ // nums에서 전 쿼리의 s-1부터 이번 쿼리의 s까지 ++(수를 더함)
                int k = nums[arr[j]]++;
                if(k == 0){                     // 만약에 수가 num에서 생겼다면
                    value++;                    // 서로 다른 수 ++;
                }
            }
        }
                                                // 두 쿼리의 s가 같을 경우에는 필요하지 않음
        if(qs[i-1].d > qs[i].d){                // 이번 쿼리의 d가 전 쿼리의 d보다 작을 때
            for(int j = qs[i-1].d ; j > qs[i].d ; j--){ //  nums에서 전 쿼리의 d 부터 이번 쿼리의 d+1까지 --(수를 없앰)
                int k = nums[arr[j]]--;
                if(k == 1){                     // 만약에 수가 num에서 없어졌다면 
                    value--;                    // 서로 다른 수--
                }
            }
        }
        else if(qs[i-1].d < qs[i].d){           // 이번 쿼리의 d가 전 쿼리의 d보다 클 때
            for(int j = qs[i-1].d+1; j <= qs[i].d ; j++){ // nums에서 전 쿼리의 d+1부터 이번 쿼리의 d까지 ++(수를 더함)
                int k = nums[arr[j]]++; 
                if(k == 0){                     // 만약에 수가 num에서 생겼다면
                    value++;                    // 서로 다른 수 ++;
                }
            }
        }
                                                // 두 쿼리의 d가 같을 경우에는 필요하지 않음
        qs[i].value = value;                    // 쿼리에 정답을  저장
    }
    sort(qs, qs+q, sbnf);                       // 다시 쿼리의 순서 순으로 정렬
    for(int i = 0 ; i < q ; i++){               
        cout << qs[i].value << "\n";            // 순서대로 출력
    }
}

정렬 시 비교 함수는 반드시 strict weak ordering을 만족해야 합니다. 그 필수 조건 중 하나는 a < b == true이고 b < a == true인 경우가 없어야 한다는 것인데, 이 코드의 경우 두 원소가 나타내는 범위가 동일할 시에 어느 순서로 비교해도 34번째 줄에 의해 true가 반환되기 때문에 라이브러리는 비교 함수가 잘못된 것으로 판단하고 에러를 발생시킨 것입니다.

wnsgur1714 4년 전 0

해결되었습니다!

앞으로 sort함수를 사용할 때는 이 점을 꼭 명심하고 사용해야 될 것 같네요.

감사합니다.

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

문제

문제

출처

ICPC

런타임 에러가 나는 이유가 궁금합니다..

wnsgur1714 4년 전 0

djm03178 4년 전 1

wnsgur1714 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말