글 읽기 - 10223번 문제 질문좀 부탁드려용!

mendou12 8년 전 0

콩나물[1]부터 콩나물[C[i]]까지 i만큼 증가시킨 뒤에,

콩나물[1]부터 콩나물[C[i]]까지의 배열을 Arr1

콩나물[C[i]+1]부터 콩나물[1]보다 작은 값이 보이면 거기서부터,

콩나물[C[i]]의 값보다 큰 값이 나올 때까지의 배열을 Arr2라고 할게용

Arr1과 Arr2를 소트(이 부분은 Arr1과 Arr2가 둘다 정렬되어있기 때문에 Arr1과 Arr2의 길이 시간만큼 걸리니깐)

이걸 D만큼 반복하면

O(N*D)시간 안에 해결하는 알고리즘을 구현했는데

자꾸 시간초과가 뜨네용.

더 효율적인구현 방법이 있나요?

void work()
{
	//입력 받기
	int N, D, a, b;
	ll s;
	cin >> N >> D >> s >> a >> b;
	
	//초기화
	int *C;
	C = new int[D + 1];
	int *K;
	K = new int[D + 1];
	vector<int> arr(N + 1);

	for (int i = 1; i <= D; i++) {
		C[i] = (s % N) + 1;
		s = ((ll)(s * a + b) % 1000000007);
		K[i] = (s % N) + 1;
		s = ((ll)(s * a + b) % 1000000007);
	}


	int day = 1;
	ll ret = 0;
	vector<int> tempArr(100000);
	int temp;
	while (day <= D) {

		//1부터 C[day]까지 증가시킴
		for (int i = 1; i <= C[day]; i++)
			arr[i] += day;

		//두 배열을 머지함
		temp = arr[1];
		int tempsize = 0;
		auto y = find_if(arr.begin() + 1 + C[day], arr.end(), [temp](int x) {return (x <= temp); });
		temp = arr[C[day]];
		auto yend = find_if(y, arr.end(), [temp](int x) {return x > temp; });
		auto xend = arr.begin() + 1 + C[day];
		auto x = arr.begin() + 1;


		while (y != yend && x != xend)
		{
			if (*x <= *y)
			{
				tempArr[tempsize++] = *x;
				x++;
			}
			else
			{
				tempArr[tempsize++] = *y;
				y++;
			}
		}
		while (x != xend)
		{

			tempArr[tempsize++] = *x;
			x++;
		}
		while (y != yend)
		{
			tempArr[tempsize++] = *y;
			y++;
		}

		copy(tempArr.begin(), tempArr.begin() + tempsize, arr.begin()+1);

		//K[day]번째 값을 찾아서 추가
		ret += arr[K[day]];
		
		day++;
	}
	cout << ret << endl;
}

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

문제

문제

출처

ICPC

10223번 문제 질문좀 부탁드려용!

mendou12 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말