Submission #12153

#	Time	Username	Problem	Language	Result	Execution time	Memory
12153		gs13105	전선 연결하기 (GA9_wire)	C++98	0 / 100	0 ms	6516 KiB

wire

#include <stdio.h>
#include <stack>

std::stack<int> s1;
std::stack<int> s2;
int arr[600001];
int idx[300001][2];
char res[600002];

int main()
{
	bool u=1;
	int n,x,i,j;
	scanf("%d",&n);
	for(i=1;i<=2*n;i++)
	{
		scanf("%d",&arr[i]);
		idx[arr[i]][!!idx[arr[i]][0]]=i;
	}
	s1.push(2*n+1);
	s2.push(2*n+1);
	for(i=1;i<=2*n;i++)
	{
		if(s1.top()==i)
			s1.pop();
		if(s2.top()==i)
			s2.pop();
		if(res[i])
			continue;
		x=idx[arr[i]][1];
		if(x>s1.top()&&x>s2.top())
		{
			printf("IMPOSSIBLE");
			return 0;
		}
		if(u&&x<s1.top()||!u&&x>s2.top())
		{
			u=1;
			s1.push(x);
			res[i]=res[x]='^';
		}
		else
		{
			s2.push(x);
			res[i]=res[x]='v';
			u=0;
		}
	}
	printf("%s",res+1);
	return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 15
• Subtask 3: 0 / 37
• Subtask 4: 0 / 39