Problem C_Bathroom Stalls.c

[Codejam_2017]Problem C_Bathroom Stalls.c

#pragma warning (disable:4996)
#include <stdio.h>
/*
 * 속도 : O(log K)
 * 메모리 : O(log N)
 */
struct STALL{
	long long n;
	long long k;
};
struct STALL stall_q[1000];
long long N, K;
int r, w;
int index_search(long long key) {
	int l, h, m;
	l = w;
	h = r;
	while (l <= h) {
		m = (l + h) / 2;
		if (stall_q[m].n < key) {
			l = m + 1;
		}
		else if (stall_q[m].n > key) {
			h = m - 1;
		}
		else {
			return m;
		}
	}
	return -1;
}
void init() {
	for (int i = 0; i < 1000; ++i) {
		stall_q[i].n = 0;
		stall_q[i].k = 0;
	}
}
void solve(int t) {
	long long k, n;
	long long sum_k = 0;
	r = w = 999;
	stall_q[w--] = {N,1};
	while (r > w) {
		 struct STALL temp = stall_q[r--];
		 n = temp.n;
		 k = temp.k;
		 sum_k += k;
		 if (sum_k >= K) {
			 printf("Case #%d: %lld %lld\n", t + 1, n/2, (n-1)/2);
			 return;
		 }
		 if (n / 2 >= 0) {
			 int ix = index_search(n/2);
			 if (ix == -1) ix = w--;
			 stall_q[ix].n = n/2;
			 stall_q[ix].k += k;

		 }
		 if ((n - 1) / 2 >= 0) {
			 int ix = index_search((n - 1) / 2);
			 if (ix == -1) ix = w--;
			 stall_q[ix].n = (n - 1) / 2;
			 stall_q[ix].k += k;
		 }
	}
	printf("Case #%d: %lld %lld\n", t + 1, n / 2, (n - 1) / 2);
	return;
}
int main() {
	int testcase;
	scanf("%d", &testcase);
	for (int i = 0; i < testcase; ++i) {
		scanf("%lld %lld", &N, &K);
		solve(i);
		init();
	}
}