PKU 1089. Intervals. [판정:WA]

위의 3건이 가장 최근에 제출해본 것입니다

그중 첫번째(Run ID: 5178307)는 검토해보니 정말 틀린부분이 있어서 WA가 났고

두번째(Run ID: 5192652)는 검토해보니 최악의 경우 O(n²)까지도 나올지도 모르겠더군요
(무작정 입력을 받아서 전부 정렬한 뒤에 겹치는 부분을 출력에서 생략하는 방식이라 -_-;)


그래서 팀블로그에 가장 마지막으로 끄적인 Intervals 풀이의 알고리즘과 유사하게 풀어보았습니다만
왜 WA가 또-_- 나오는지는 모르겠네요

#include <iostream> using namespace std; class Interval { public: int lower; int upper; Interval() { lower = 0, upper = 0; } Interval( int a, int b ) { lower = a, upper = b; } }; class Queue { public: Interval *list; // circular array int size; int exist; int front; int back; Queue() { size = 0, exist = 0, front = 0, back = 0, list = NULL; } Queue( int n ) { size = n, exist = 0, front = 0, back = 0, list = new Interval[n]; } void push( Interval in ) { list[back % size] = in; back = ++back % (size * 2); exist++; } Interval pop() { Interval oldvalue; oldvalue = list[front % size]; front = ++front % (size * 2); exist--; return oldvalue; } }; int main() { int n; int i, j, k; int actual; // revised index scanf("%d", &n); Queue q(n); // input intervals for( i = 0; i < n; i++ ) { Interval receive; scanf("%d %d", &receive.lower, &receive.upper); for( j = 0; j < q.exist; j++ ) { int diff1, diff2; actual = (j + q.front) % q.size; diff1 = q.list[actual].upper - receive.lower; diff2 = q.list[actual].lower - receive.upper; if( diff1 > 0 ) diff1 = !!diff1; // become sign: prevent overflow if( diff2 > 0 ) diff2 = !!diff2; // same intention if( diff1 * diff2 <= 0 ) // intersection is exist { Interval temp; k = 0; for( ; k < j; k++ ) { temp = q.pop(); q.push(temp); } if( k != 0 ) j -= k; else { temp = q.pop(); if( receive.lower > temp.lower ) receive.lower = temp.lower; if( receive.upper < temp.upper ) receive.upper = temp.upper; } j--; // repeat } } q.push(receive); } // sort intervals: selection sort int min, minindex; for( i = 0; i < q.exist - 1; i++ ) { actual = (i + q.front) % q.size; min = q.list[actual].lower; minindex = actual; for( j = i; j < q.exist; j++ ) { k = (j + q.front) % q.size; if( min > q.list[k].lower ) { min = q.list[k].lower; minindex = k; } } if( minindex != actual ) { swap( q.list[actual].lower, q.list[minindex].lower ); swap( q.list[actual].upper, q.list[minindex].upper ); } } // print intervals for( i = 0; i < q.exist; i++ ) { actual = (i + q.front) % q.size; printf("%d %d\n", q.list[actual].lower, q.list[actual].upper); } return 0; }

지난번에 올려놓은 풀이는 리스트를 직접 만들어서 사용했지만
linked list방식이 다소 불안정한 면이 있는 것 같아서

이번에는 환형 배열을 사용한 큐를 택했는데 -_-;

뭔가 특수한 케이스가 있어서 그른지
아니면 소스가 잘못된건지 ㅠ