글 읽기 - 메모리초과, 시간초과를 도저히 못잡겠습니다 ㅠ...

jh20s 5년 전 0

2015 ucpc ppt를 보고 해결해보려 했으나 메모리초과 or 시간초과를 도저히 못잡겠습니다 ㅠㅠ

n과 m은 4가지로 분할되는걸 저장하고, 각각 분할되어서 생기는 N,M에 대해

k값과 그 개수를 저장해주었습니다.

map은 tc가 여러개니까재활용해야만 한다 생각하는데 재활용하게되면 메모리초과가

다시 만들면 시간초과가...

map<Pair,map<long long, long long>> m 이게 메모리 초과의 원인일텐데

이 방법 말곤 도저히 방법이 떠오르지가 않네요 ㅠㅠ...

아예 알고리즘이 잘못된건가요...ㅠ?

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<tuple>
#include<string>
#include<map>
#include<queue>
#include<functional>
#include<math.h>
#include<list>
using namespace std;
#define inf 1000000000

typedef pair<long long, long long> Pair;
map<Pair, map<long long, long long>> m;
int mod = 1234567891;

void getm(long long R, long long C, long long a, long long c) {
	for (auto it : m[{a, c}]) {
		m[{R, C}][it.first] = (m[{R, C}][it.first]+it.second)%mod;
	}
}

void go(long long R, long long C) {
	if (m.count({ R,C }) == 1) return;
	long long a = R / 2, b = R / 2 + R % 2;
	long long c = C / 2, d = C / 2 + C % 2;
	long long k;


	if(a != 0 && c != 0){
		if (a == 1 ||c==1) {
			k = max(a, c);
			m[{R, C}][k]++;
		}
		else {
			go(a, c);
			getm(R, C, a, c);
		}
	}
	if (a != 0 && d != 0) {
		if (a == 1 || d == 1) {
			k = max(a, d);
			m[{R, C}][k]++;
		}
		else {
			go(a, d);
			getm(R, C, a, d);
		}
	}
	if (b != 0 && c != 0) {
		if (b == 1 || c == 1) {
			k = max(b, c);
			m[{R, C}][k]++;
		}
		else go(b, c), getm(R, C, b, c);
	}
	if (b != 0 && d != 0) {
		if (b == 1 || d == 1) {
			k = max(b, d);
			m[{R, C}][k]++;
		}
	}
	else go(b, d), getm(R, C, b, d);
}


int main(void) {
	int tc;
	scanf("%d", &tc);
	while (tc--) {
		long long r, c;
		m.clear();
		scanf("%lld %lld", &r, &c);
		go(r, c);
		printf("%d\n", m[{r, c}].size());
		for (auto it : m[{r, c}])
			printf("%lld %lld\n", it.first, it.second%mod);
	}
}

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

문제

문제

출처

ICPC

메모리초과, 시간초과를 도저히 못잡겠습니다 ㅠ...

jh20s 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말