글 읽기 - 제출만하면 시간초과가 뜹니다

backjun 3년 전 0

도와주세요

이동하고 높이에 따라서 1인경우는 바로 Tball에 넣고 아니면 Trans함수에서 분배하는 것으로 짰습니다 예제를 돌려보면서 로직에는 이상이 없을 듯하지만 제출만하면 시간초과가 뜹니다.

#include<stdio.h>
#include<string.h>

typedef struct Ball
{
	int r, c, d, m, s;
}Ball;

Ball ball[51 * 51 * 51 * 51], Tball[51 * 51 * 51 * 51];
int map[51][51][51 * 51], h[51][51], dx[8] = { -1, -1, 0, 1, 1, 1, 0, -1 }, dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int n, m, k, tm;

void Move(int index)
{
	ball[index].r += dx[ball[index].d] * ball[index].s, ball[index].c += dy[ball[index].d] * ball[index].s;
	if (ball[index].r > n) ball[index].r -= n;
	if (ball[index].r < 1) ball[index].r += n;
	if (ball[index].c > n) ball[index].c -= n;
	if (ball[index].c < 1) ball[index].c += n;
	map[ball[index].r][ball[index].c][++h[ball[index].r][ball[index].c]] = index;
}

void Trans(int r, int c)
{
	int sm = 0, ss = 0, chk = 0, a = 0, b = 0;
	for (int i = 1; i <= h[r][c]; i++)
	{
		sm += ball[map[r][c][i]].m;//질량을더해주는 부분
		ss += ball[map[r][c][i]].s;//속도를 더해주는 부분
		if (ball[map[r][c][i]].d % 2 == 0) a++;//방향이 짝수인지 홀수 인지 판별해서 저장하는 곳
		else b++;
	}
	sm /= 5, ss /= h[r][c];//분배할 질량과 속도를 구하는 부분
	if (sm == 0) return;//질량이 0이라면 없앤다
	if (a==0 || b==0)
	{
		for (int i = 0; i <= 6; i += 2)
		{
			Tball[++tm].r = r, Tball[tm].c = c, Tball[tm].m = sm, Tball[tm].s = ss, Tball[tm].d = i;
		}
	}
	else
	{
		for (int i = 1; i <= 7; i += 2)
		{
			Tball[++tm].r = r, Tball[tm].c = c, Tball[tm].m = sm, Tball[tm].s = ss, Tball[tm].d = i;
		}
	}
	
}

int main(void)
{
	int sum = 0;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d%d%d%d", &ball[i].r, &ball[i].c, &ball[i].m, &ball[i].s, &ball[i].d);
		ball[i].s %= n;
	}
	for (int i = 1; i <= k; i++)
	{
		memset(map, 0, sizeof(map));
		memset(h, 0, sizeof(h));
		for (int j = 1; j <= m; j++)  Move(j);//이동을 시작하는 부분
		tm = 0;
		for (int r = 1; r <= n; r++)
		{
			for (int c = 1; c <= n; c++)
			{
				if (!h[r][c]) continue;//아무도 없는 곳
				else if (h[r][c] == 1)//한개 만 있는 경우
				{
					Tball[++tm].r = r, Tball[tm].c = c;
					Tball[tm].m = ball[map[r][c][1]].m, Tball[tm].s = ball[map[r][c][1]].s, Tball[tm].d = ball[map[r][c][1]].d;
				}
				else if(h[r][c] > 1)
				{
					Trans(r, c);//두개이상이 있는 경우
				}
			}
		}
		m = 0;
		for (int t = 1; t <= tm; t++) ball[++m] = Tball[t];
	}
	for (int t = 1; t <= m; t++) sum += ball[t].m;
	printf("%d", sum);
}

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

문제

문제

출처

ICPC

제출만하면 시간초과가 뜹니다

backjun 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말