oj.uz

답안 #56917

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
56917 2018-07-13T07:23:28 Z 정원준(#1637) 기억 압축 (JOI15_memory) C++11
100 / 100
 3408 ms 276964 KB 
#include <Memory_lib.h>
#include <bits/stdc++.h>

using namespace std;

char Get(int I);

int trans(char a){
	if(a=='[') return 0;
	if(a==']') return 3;
	if(a=='<') return 1;
	if(a=='>') return 2;
}

int pack(int s,int h,int n,int f,int e){
	//printf("%d %d %d %d %d\n",s,h,n,f,e);
	int ret=0;
	//h--;
	//n--;
	f--;
	ret+=s<<19;
	ret+=h*10200+n*100+f;
	ret<<=1;
	ret+=e;
	if(ret<0||ret>=(1<<22)) return -2;
	return ret;
}

int Memory(int N,int M){
	int ended,state,height,now,far,locvalues;
	if(M==0)
	{
		ended=0;
		state=0;
		height=0;
		now=1;
		far=0;
	}
	else
	{
		ended=M%2;
		M/=2;
		state=(M>>19);
		locvalues=(M-(state<<19));
		height=locvalues/10200;
		now=(locvalues/100)%102;
		far=locvalues%100+1;
	}

	//printf("%d %d %d %d %d\n",state,height,now,far,ended);

	if(ended)
	{
		if(now==0) 
		{
			//while(1);
			return -1;
		}
		
		if(now<1||now>N) return -2;
		
		int temp=trans(Get(now));
		if(temp<=1) height--;
		else height++;
		if(height<0) return -2;
		now--;
		return pack(state,height,now,far,ended);
	}
	
	
	if(height)
	{
		if(now<1) return -2;
		
		if(now<1||now>N) return -2;
		
		int temp=trans(Get(now));
		if(temp<=1) height--;
		else height++;
		if(height==0)
		{
			if(temp+state!=3) return -2;
			state=0;
			height=0;
			now++;
			
			return pack(state,height,now,far,ended);
		}
		else
		{
			now--;
			//printf("%lld\n",now);
			return pack(state,height,now,far,ended);
		}
	}
	else
	{
		if(now>far)
		{
			far=now;
			if(now>N)
			{
				far=N;
				ended=1;
				height=0;
				now--;
				return pack(state,height,now,far,ended);
			}
			else
			{
				
				if(now<1||now>N) return -2;
			
				int temp=trans(Get(now));
				if(temp<=1)
				{
					now++;
					return pack(state,height,now,far,ended);
				}
				else
				{
					state=temp;
					height=1;
					now--;
					return pack(state,height,now,far,ended);
				}
			}
		}
		else
		{
			now++;
			return pack(state,height,now,far,ended);
		}
	}
}

/*
int n,tc;
char str[111];

void E(int x){
	printf("Wrong answer %d",x);
}

char Get(int I){
	if(I<1||I>n)
		E(3);
	return str[I-1];
}

int main()
{
	scanf("%d %d",&n,&tc);
	int i;
	for(i=1;i<=tc;i++)
	{
		scanf("%s",str);
		int mem=0,cnt=0;
		do
		{
			mem=Memory(n,mem);
			cnt++;
			if(mem<0) break;
		}while(1);
		printf("%d %d\n",mem,cnt);
	}
}*/

Compilation message

memory.cpp: In function 'int trans(char)':
memory.cpp:13:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3066 ms 276740 KB Output is correct
2 Correct 3279 ms 276740 KB Output is correct
3 Correct 2797 ms 276756 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3066 ms 276740 KB Output is correct
2 Correct 3279 ms 276740 KB Output is correct
3 Correct 2797 ms 276756 KB Output is correct
4 Correct 3150 ms 276916 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3066 ms 276740 KB Output is correct
2 Correct 3279 ms 276740 KB Output is correct
3 Correct 2797 ms 276756 KB Output is correct
4 Correct 3150 ms 276916 KB Output is correct
5 Correct 2794 ms 276916 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3066 ms 276740 KB Output is correct
2 Correct 3279 ms 276740 KB Output is correct
3 Correct 2797 ms 276756 KB Output is correct
4 Correct 3150 ms 276916 KB Output is correct
5 Correct 2794 ms 276916 KB Output is correct
6 Correct 3174 ms 276964 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3408 ms 276964 KB Output is correct

Subtask #6
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3066 ms 276740 KB Output is correct
2 Correct 3279 ms 276740 KB Output is correct
3 Correct 2797 ms 276756 KB Output is correct
4 Correct 3150 ms 276916 KB Output is correct
5 Correct 2794 ms 276916 KB Output is correct
6 Correct 3174 ms 276964 KB Output is correct
7 Correct 3408 ms 276964 KB Output is correct
8 Correct 3310 ms 276964 KB Output is correct
9 Correct 3233 ms 276964 KB Output is correct