Submission #200268

#	Time	Username	Problem	Language	Result	Execution time	Memory
200268		wjdqhdhfflavldkem12	곡선 자르기 (KOI17_cut)	C++14	35 / 100	403 ms	69116 KiB

cut

#include <stdio.h>
#include <deque>
#include <list>
#include <stack>
#include <limits.h>
#include <algorithm>

using namespace std;

typedef pair<int, int> pi;
typedef struct{
	int x1;
	int x2;
}node;

int n, size, inX, outX;
list<pi> point;
node xx[100100];
list<int> peak;
stack<list<int> ::iterator> stk;
list<int> ::iterator iter;
list<pi> ::iterator iterp;

void pushPeak(list<int> ::iterator it, int a);

bool compare(node a, node b){
	return a.x1 < b.x1;
}

int main(){
	int i;
	
	int x, y, start;
	int minx = INT_MAX, miny = INT_MAX;

	scanf("%d", &n);
	//꼭짓점 좌표 디큐에 저장, 왼쪽 아래 시작 꼭짓점 찾기
	for (i = 0; i < n; i++){
		scanf("%d %d", &x, &y);
		point.push_back(pi(x, y));
		if (x <= minx&&y <= miny){
			start = i;
			minx = x; miny = y;
		}
	}
	//왼쪽 아래를 index 0으로 두게끔 변경
	for (i = 0; i < start; i++){
		pi temp = *point.begin();
		point.push_back(temp);
		point.pop_front();
	}

	//봉우리의 왼쪽, 오른쪽 기둥 x좌표 입력
	int temp;
	iterp = point.begin();
	for (i = 0; i < n; i++){
		while (i != n&& (*iterp).second < 0){
			i++;
			iterp++;
		}
		if (i == n)
			break;
		xx[size].x1 = (*iterp).first;
		while (i != n && (*iterp).second > 0){
			i++;
			iterp++;
		}
		if (i == n)
			break;
		xx[size].x2 = (*iterp).first;
		if (xx[size].x1>xx[size].x2){
			temp = xx[size].x1;
			xx[size].x1 = xx[size].x2;
			xx[size].x2 = temp;
		}
		size++;
		iterp++;
	}
	point.clear();

	//봉우리의 왼쪽기둥 x좌표 기준 오름차순 정렬
	sort(xx, xx+size, compare);

	//봉우리를 x좌표 기준으로 정렬, INT_MIN으로 봉우리를 구분한다.
	iter = peak.begin();
	for (i = 0; i < size; i++){
		if (stk.empty()){
			iter = peak.end();
			pushPeak(iter, i);
			iter--; iter--;
			stk.push(iter);
		}
		else{
			iter = stk.top();
			while (*iter < xx[i].x1){
				stk.pop();
				if (stk.empty()){
					iter = peak.end();
					break;
				}
				iter = stk.top();
			}
			pushPeak(iter, i);
			iter--; iter--;
			stk.push(iter);
		}
	}

	//peak 처음부터 끝까지 검사하며 answer 검사, 
	iter = peak.begin();
	list<int> ::iterator iter2;
	int num = 0; //미완성 봉우리 갯수
	while (iter != peak.end()){
		if (*iter == INT_MIN){
			num++;
		}
		else{
			num--;
			iter2 = iter;
			iter2--; iter2--;
			if (*iter2 == INT_MIN)
				inX++;
		}
		if (num == 0)
			outX++;
		iter++; iter++;
	}

	printf("%d %d\n", outX, inX);

	return 0;
}

void pushPeak(list<int> ::iterator it, int a){
	peak.insert(it, INT_MIN);
	peak.insert(it, xx[a].x1);
	peak.insert(it, xx[a].x2);
	peak.insert(it, INT_MIN);
	return;
}

Compilation message (stderr)

cut.cpp: In function 'int main()':
cut.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
cut.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~
cut.cpp:47:16: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
  for (i = 0; i < start; i++){
              ~~^~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 24 / 24
• Subtask 3: 0 / 65