Submission #65404026

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
struct yagi_s {
  int64_t pos;
  int id;
};
int cmp(const void* x, const void* y) {
  struct yagi_s a = *(const struct yagi_s*)x, b = *(const struct yagi_s*)y;
  return a.pos < b.pos ? -1 : a.pos > b.pos;
}
int N;
int64_t A[212345];
int Q;
int64_t B[212345];
struct yagi_s y[212345];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

struct yagi_s {
	int64_t pos;
	int id;
};

int cmp(const void* x, const void* y) {
	struct yagi_s a = *(const struct yagi_s*)x, b = *(const struct yagi_s*)y;
	return a.pos < b.pos ? -1 : a.pos > b.pos;
}

int N;
int64_t A[212345];
int Q;
int64_t B[212345];

struct yagi_s y[212345];

int main(void) {
	int i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%" SCNd64, &A[i]) != 1) return 1;
		y[i + 1].pos = A[i];
		y[i + 1].id = i + 1;
	}
	if (scanf("%d", &Q) != 1) return 1;
	for (i = 0; i < Q; i++) {
		if (scanf("%" SCNd64, &B[i]) != 1) return 1;
	}

	qsort(y + 1, N, sizeof(*y), cmp);
	y[0].pos = -INT64_C(3123456789012345678);
	y[N + 1].pos = INT64_C(3123456789012345678);

	for (i = 0; i < Q; i++) {
		int le = 0, g = N + 1;
		while (le + 1 < g) {
			int m = le + (g - le) / 2;
			if (y[m].pos <= B[i]) le = m; else g = m;
		}
		if (
			B[i] - y[le].pos < y[g].pos - B[i] ||
			(
				B[i] - y[le].pos == y[g].pos - B[i] &&
				y[le].id < y[g].id
			)
		) {
			printf("%d\n", y[le].id);
			y[le].pos = B[i];
		} else {
			printf("%d\n", y[g].id);
			y[g].pos = B[i];
		}
	}

	return 0;
}

Submission Info

Judge Result