글 읽기 - 2493 탑 배열두개로 풀어봤습니다

jhko00 7년 전 0

탑의 크기와 번호를 pair p배열에 저장하고

p배열 마지막 탑을 q로 옮기면서 q에 p보다 큰 탑이 오면

re배열에 큰 탑의 번호를 저장시켰습니다

앞에 자신보다 큰 탑이 없는 탑은 h배열 값을 1로 만들어 q배열에 오면

바로 re에 0을 저장시키고 뺐습니다

예제 및 임의의 수로 테스트를 해봐도 값이 잘 나오는데

어느 부분에서 문제가 있는건지 모르겠습니다

코드가 좀 더럽지만 봐주시고 문제를 알려주시면 감사드립니다

#include <stdio.h>
#include <algorithm>
using namespace std;
pair<long long int,long long int > p[500000],q[500000];
long long int n,i,tower,s1,s2,f1,f2,re[500000],ss,h[500000]={0,},maxi;
int main(){
	scanf("%lld",&n);
	for(i=0;i<n;i++){
		scanf("%lld",&tower);
		p[i]=make_pair(tower,i+1);
		if(i==0 || maxi<tower){
			maxi=tower;
			h[i]=1;
		}
	}
	s1=0;f1=n-1;
	s2=0;f2=-1;
	while(1){
		if(f1==s1-1 && f2==s2-1)
			break;
		if(f1!=s1-1){
			q[f2+1]=make_pair(p[f1].first,p[f1].second);
			f2+=1;f1-=1;
		}
		while(1){
			ss=s2;
			if(h[q[s2].second-1]==1){
				re[q[s2].second-1]=0;
				s2+=1;
			}
			if(f2>s2 && q[f2].first>=q[s2].first){
				re[q[s2].second-1]=q[f2].second;
				s2+=1;
			}
			if(s2==ss)
				break;
		}
	}
	printf("%lld",re[0]);
	for(i=1;i<n;i++)
		printf(" %lld",re[i]);
	printf("\n");
	return 0;
}

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

문제

문제

출처

ICPC

2493 탑 배열두개로 풀어봤습니다

jhko00 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말