글 읽기 - 5676 음주코딩 시간초과 or 틀렸습니다

daniel00 4년 전 0

첨부의 코드 86/87 번에 주석으로 표시한것 처럼,

86 번 라인인 cin을 사용하면 시간초과,

87 라인인 scanf를 사용하면 틀렸습니다 가 발생하네요.

혹시 제가 무슨 실수를 하고 있는걸까요?

풀이 방법은 펜윅트리 두개를 사용해서 각각 음수의 개수, 0의 개수를 저장하여 처리하는 방식입니다.

여러분들의 조언 부탁드립니다. 감사합니다.

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

#define MAXN    100000

int BIT_NEG[MAXN + 1];
int BIT_ZERO[MAXN + 1];

int SRC[MAXN + 1];

int N, K;
char cmd;
int a, b;

using namespace std;

void updateBIT(int* arrBIT, int idx, int val)
{
	while (idx <= N)
	{
		arrBIT[idx] += val;
		idx += (idx & -idx);
	}
}

int getSum(int* arrBIT, int idx)
{
	int ans = 0;

	while (idx >= 1)
	{
		ans += arrBIT[idx];
		idx -= (idx & -idx);
	}

	return ans;
}

int main()
{
	//ios::ios_base::sync_with_stdio(false);
	//cin.tie(NULL);

#ifndef ONLINE_JUDGE
	freopen("test_input.txt", "r", stdin);
#endif

	while (scanf("%d %d", &N, &K) != EOF)
	{
		memset(SRC, 0x00, MAXN + 1);
		memset(BIT_ZERO, 0x00, MAXN + 1);
		memset(BIT_NEG, 0x00, MAXN + 1);

		for (int i = 1; i <= N; i++)
		{
			scanf("%d", &SRC[i]);
			//cin >> SRC[i];

			if (SRC[i] < 0)
			{
				updateBIT(BIT_NEG, i, 1);   //음수개수
				updateBIT(BIT_ZERO, i, 0);
			}
			else if (SRC[i] > 0)
			{
				updateBIT(BIT_NEG, i, 0);
				updateBIT(BIT_ZERO, i, 0);
			}
			else if (SRC[i] == 0)
			{
				updateBIT(BIT_NEG, i, 0);
				updateBIT(BIT_ZERO, i, 1);  //0 개수
			}

		}

		//read command
		int idx, val;
		int start, end;
		int result;
		int neg_cnt;
		int zero_cnt;

		for (int i = 1; i <= K; i++)
		{
			//cin >> cmd >> a >> b;				//시간초과
			scanf("%s %d %d", &cmd, &a, &b);	//틀렸습니다
			

			if (cmd == 'C')
			{
				idx = a;
				val = b;

				if (val < 0)
				{
					if (SRC[idx] > 0)
					{
						updateBIT(BIT_NEG, idx, 1);
					}
					else if (SRC[idx] < 0)
					{
						;
					}
					if (SRC[idx] == 0)
					{
						updateBIT(BIT_NEG, idx, 1);
						updateBIT(BIT_ZERO, idx, -1);
					}
				}
				else if (val == 0)
				{
					if (SRC[idx] < 0)
					{
						updateBIT(BIT_NEG, idx, -1);
						updateBIT(BIT_ZERO, idx, 1);
					}
					else if (SRC[idx] > 0)
					{
						updateBIT(BIT_ZERO, idx, 1);
					}
					else if (SRC[idx] == 0)
					{
						;
					}
				}
				else if (val > 0)
				{
					if (SRC[idx] < 0)
					{
						updateBIT(BIT_NEG, idx, -1);
					}
					else if (SRC[idx] == 0)
						updateBIT(BIT_ZERO, idx, -1);
				}

				SRC[idx] = val;
			}
			else if (cmd == 'P')
			{
				start = a;
				end = b;
				// printf("start end : %d %d\n", start, end);

				zero_cnt = getSum(BIT_ZERO, end) - getSum(BIT_ZERO, start - 1);
				neg_cnt = getSum(BIT_NEG, end) - getSum(BIT_NEG, start - 1);

				/*cout << "zero_cnt : " << zero_cnt << endl;
				cout << "neg_cnt : " << neg_cnt << endl;*/

				if (zero_cnt > 0)            //0이 하나라도 있으면
					printf("0");
				else if (neg_cnt % 2 == 0)  //음수가 짝수개이면
					printf("+");
				else
					printf("-");
				//cout << endl;
			}
		}

		printf("\n");
		//cout << endl;
	}



	return 0;
}

daniel00 4년 전 1

자답입니다.

배열 초기화를 잘못하고 있었습니다.

sizeof로 다시 초기화를 하니 정상 동작하네요.

그리고, 아래 어떤분께서 테스트용 파일을 링크해 주셔서 문제를 찾을 수 있었습니다.

혹시 필요하신 분이 계실까 싶어서 여기에도 남겨봅니다.

참고하세요.

http://gooddaytocode.blogspot....

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

문제

문제

출처

ICPC

5676 음주코딩 시간초과 or 틀렸습니다

daniel00 4년 전 0

daniel00 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말