글 읽기 - 모르겠습니다.

wksms21 5년 전 0

구간의 사이즈를 우선순위로 사용하는 힙을 통해 문제를 접근하였습니다.
테스트 케이스와 같이 M이 10^5이하인 경우에는 통과하지만 M이 너무 크네요...
어떤 방식으로 접근해야할까요?

#include <stdio.h>

typedef long long ll;

struct h {
	ll s, e, size;
	bool operator < (const h &other) {
		if (size == other.size) return s > other.s;
		return size < other.size;
	}
	bool operator > (const h &other) {
		if (size == other.size) return s < other.s;
		return size > other.size;
	}
};

h heap[1000010];
ll size;

void push(h x) {
	ll i = ++size;
	for (; i != 1 && x > heap[i / 2]; i /= 2) heap[i] = heap[i / 2];
	heap[i] = x;
}

h top() {
	if (!size) return{ 0, 0, 0 };
	ll parent = 1, child = 2;
	h data = heap[parent];
	h leaf = heap[size--];
	while (child <= size) {
		if (child < size && heap[child] < heap[child + 1]) child++;
		if (leaf > heap[child]) break;
		heap[parent] = heap[child];
		parent = child;
		child *= 2;
	}
	heap[parent] = leaf;
	return data;
}

ll M, N, Q;
ll A[300010];
ll B[300010];
ll ans[300010];

int main()
{
	scanf("%lld%lld%lld", &N, &M, &Q);
	ll s, e, i, j;
	for (i = 0; i < M; i++) {
		scanf("%lld", A + i);
		if (i == 0) {
			s = 1;
			e = A[i] - 1;
		}
		else {
			s = A[i - 1] + 1;
			e = A[i] - 1;
		}
		push({ s, e, e - s + 1 });
		ans[i + 1] = A[i];
	}
	s = A[i - 1] + 1;
	e = N;
	i++;
	ans[i + 1] = A[i];
	push({ s, e, e - s + 1 });
	for (j = 0; j < Q; j++) scanf("%lld", B + j);
	while (size) {
		h tmp = top();
		ll s = tmp.s;
		ll e = tmp.e;
		ll m = (s + e) / 2;
		ans[i++] = m;
		if (s <= m - 1) push({ s, m - 1, m - 1 - s + 1 });
		if (e >= m + 1) push({ m + 1, e, e - (m + 1) + 1 });
	}
	for (j = 0; j < Q; j++) printf("%lld\n", ans[B[j]]);
	return 0;
}

gee308 4년 전 0

모르겠습니다2

아직 이 문제에 흥미 있으신가요? 못푼 문제로 남겨두는게 좀 찝찝하네요...

풀이를 보니 모든 학생의 자리를 저장하는 식으로 하신거 같은데,

이미 아시겠지만 M의 범위가 10^14까지 가버리니 배열을 만들수가 없죠..

그래서 떠오른 풀이가 첫번째 자리부터 계산해서 바로바로 출력하는 방식을 생각해봤습니다.

Heap 사이즈는 일단 512MB가 허용하는 최대로 잡았구요...

결과는 시간초과...

#include <stdio.h>
#include <iostream>

#define maxnum 1000*1000*33 //1000*1000*35 메모리 초과 512MB넘어감
#pragma warning(disable : 4996)

typedef struct node {
	long long x;
	long long length = 0;
};

class heap
{
private:
	node arr[maxnum];
	int wp = 0;

public: 
	int compare_node(int a, int b) //a가크면 1
	{
		if (arr[a].length > arr[b].length) return 1;
		else if (arr[a].length == arr[b].length || arr[a].x < arr[b].x) return 1;
		else 0;
	}

	int compare_node2(int a, int b) //a가크면 1 b가크면 -1 같으면 0
	{
		if (arr[a].length > arr[b].length) return 1;
		else if (arr[a].length < arr[b].length) return -1;
		else if (arr[a].length == arr[b].length)
		{
			if (arr[a].x < arr[b].x) return 1;
			else if (arr[a].x > arr[b].x) return -1;
			else return 0;
		}
	}

	void swap(int a, int b)
	{
		long long temp1 = arr[a].length;
		arr[a].length = arr[b].length;
		arr[b].length = temp1;

		long long temp2 = arr[a].x;
		arr[a].x = arr[b].x;
		arr[b].x = temp2;
	}

	void insert_node(long long px, long long plength)
	{
		if (maxnum > wp + 1)
		{
			arr[++wp].x = px;
			arr[wp].length = plength;

			int n = wp;
			int p = wp / 2;
			while (p > 0 && compare_node(n, p) == 1)
			{
				swap(n, p);

				n = p;
				p /= 2;
			}
		}
	}

	void pop(long long* x, long long* len)
	{
		if (wp == 0) return;

		*x = arr[1].x;
		*len = arr[1].length;

		arr[1].length = arr[wp].length;
		arr[1].x = arr[wp--].x;

		int n = 1, l = 2, r = 3, c;

		while (l <= wp)
		{
			if (l == wp) c = l;
			else if (compare_node(l, r) == 1) c = l;
			else c = r;

			if (compare_node(c, n) == 1)
			{
				swap(c, n);

				n = c;
				l = n * 2;
				r = l + 1;
			}
			else break;
		}
	}

	bool isempty()
	{
		if (wp == 0) return true;
		else return false;
	}
};


int main(void)
{
	long long M;
	int N, Q; //컴퓨터 수, 자리 이미 잡은 수, 친구의 수
	scanf("%lld %d %d", &M, &N, &Q);
	heap h;

	long long before = 1;
	long long* people = new long long[N + 3];
	for (int i = 0; i < N; i++)
	{
		long long temp;
		scanf("%lld", &temp);

		people[i] = temp;

		if (before < temp)
			h.insert_node(before, temp - before); //연속된 빈자리의 시작점 before, 길이 heap에 push

		before = temp + 1;
	}
	if (before <= M) h.insert_node(before, M - before + 1); //마지막 연속된 빈자리의 시작점 before, 길이 heap에 push
	//입력

	long long current = N; //temp가 끝나면 current는 N부터 시작
	for (int i = 0; i < Q; i++)
	{
		long long temp;
		scanf("%lld", &temp);

		if (temp < N) printf("%lld\n", people[temp - 1]); //입력으로 주어진 범위 안에 있을 경우 people 출력
		else 
		{
			long long x, len, c;
			do
			{
				h.pop(&x, &len);
				current++;

				c = x + (len - 1) / 2; //current 번째놈이 앉을 컴퓨터 좌표

				if (c != x) h.insert_node(x, c - x);
				if (c != x + len - 1) h.insert_node(c + 1, x + len - c - 1);
			} while (temp > current); 

			printf("%lld\n", x + (len - 1) / 2);
		}
	}
}

danimartinwife 4년 전 0

gee308

저도 비슷하게 풀어서 실패했는데 맞으신 분들 명단 보니까 대부분 코드포스 레드 수준의 어나더 레벨들이라... 저같은 사람이 도전할 문제는 아닌거 같습니다. 코드포스 레드 정도면 거의 왠만한 대형 프로그래밍 대회 입상권이라는데;;; 그냥 코딩테스트 준비를 위해서라면 그 시간에 다른 문제를 더 푸는게 나은거 같네요.

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

문제

문제

출처

ICPC

모르겠습니다.

wksms21 5년 전 0

gee308 4년 전 0

danimartinwife 4년 전 0

gee308

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말