Submission #67088152


Source Code Expand

Copy
#include <stdio.h>
#define INF 1010101010
#define KI_MAX (1 << 17) /* 131072 */
int ki[KI_MAX * 2 - 1];
void ki_add(int pos, int value) {
pos += KI_MAX - 1;
ki[pos] += value;
do {
int a, b;
pos = (pos - 1) / 2;
a = ki[pos * 2 + 1];
b = ki[pos * 2 + 2];
ki[pos] = a <= b ? a : b;
} while (pos > 0);
}
int ki_get_i(int idx, int ss, int se, int qs, int qe) {
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include <stdio.h>

#define INF 1010101010

#define KI_MAX (1 << 17) /* 131072 */

int ki[KI_MAX * 2 - 1];

void ki_add(int pos, int value) {
	pos += KI_MAX - 1;
	ki[pos] += value;
	do {
		int a, b;
		pos = (pos - 1) / 2;
		a = ki[pos * 2 + 1];
		b = ki[pos * 2 + 2];
		ki[pos] = a <= b ? a : b;
	} while (pos > 0);
}

int ki_get_i(int idx, int ss, int se, int qs, int qe) {
	if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		return ki[idx];
	} else if (se <= qs || qe <= ss) { /* 完全に外れている */
		return INF;
	} else {
		int sm = ss + (se - ss) / 2;
		int l = ki_get_i(idx * 2 + 1, ss, sm, qs, qe);
		int r = ki_get_i(idx * 2 + 2, sm, se, qs, qe);
		return l <= r ? l : r;
	}
}

int ki_get(int qs, int qe) {
	return ki_get_i(0, 0, KI_MAX, qs, qe);
}

int main(void) {
	int N, Q;
	int i;
	if (scanf("%d%d", &N, &Q) != 2) return 1;
	for (i = 0; i < Q; i++) {
		int X;
		int ans;
		if (scanf("%d", &X) != 1) return 1;
		if (X == 0) {
			/* 「そこまでの最小値を求めると、全体の最小値になる」最初の箱に入れる */
			int min = ki_get(1, N + 1);
			int no = 0, yes = N;
			while (no + 1 < yes) {
				int m = no + (yes - no) / 2;
				if (ki_get(1, m + 1) == min) yes = m; else no = m;
			}
			ans = yes;
		} else {
			ans = X;
		}
		ki_add(ans, 1);
		printf(" %d" + !i, ans);
	}
	putchar('\n');
	return 0;
}

Submission Info

Submission Time
Task B - Reverse Proxy
User mikecat
Language C (gcc 12.2.0)
Score 200
Code Size 1447 Byte
Status AC
Exec Time 1 ms
Memory 1772 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 200 / 200
Status
AC × 3
AC × 42
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 1728 KiB
sample_02.txt AC 1 ms 1768 KiB
sample_03.txt AC 1 ms 1616 KiB
test_01.txt AC 1 ms 1648 KiB
test_02.txt AC 1 ms 1740 KiB
test_03.txt AC 1 ms 1772 KiB
test_04.txt AC 1 ms 1692 KiB
test_05.txt AC 1 ms 1732 KiB
test_06.txt AC 1 ms 1652 KiB
test_07.txt AC 1 ms 1772 KiB
test_08.txt AC 1 ms 1616 KiB
test_09.txt AC 1 ms 1656 KiB
test_10.txt AC 1 ms 1668 KiB
test_11.txt AC 1 ms 1744 KiB
test_12.txt AC 1 ms 1616 KiB
test_13.txt AC 1 ms 1652 KiB
test_14.txt AC 1 ms 1756 KiB
test_15.txt AC 1 ms 1752 KiB
test_16.txt AC 1 ms 1724 KiB
test_17.txt AC 1 ms 1748 KiB
test_18.txt AC 1 ms 1656 KiB
test_19.txt AC 1 ms 1648 KiB
test_20.txt AC 1 ms 1748 KiB
test_21.txt AC 1 ms 1768 KiB
test_22.txt AC 1 ms 1616 KiB
test_23.txt AC 1 ms 1748 KiB
test_24.txt AC 1 ms 1660 KiB
test_25.txt AC 1 ms 1624 KiB
test_26.txt AC 1 ms 1628 KiB
test_27.txt AC 1 ms 1604 KiB
test_28.txt AC 1 ms 1672 KiB
test_29.txt AC 1 ms 1612 KiB
test_30.txt AC 1 ms 1652 KiB
test_31.txt AC 1 ms 1632 KiB
test_32.txt AC 1 ms 1740 KiB
test_33.txt AC 1 ms 1760 KiB
test_34.txt AC 1 ms 1648 KiB
test_35.txt AC 1 ms 1752 KiB
test_36.txt AC 1 ms 1728 KiB
test_37.txt AC 1 ms 1668 KiB
test_38.txt AC 1 ms 1616 KiB
test_39.txt AC 1 ms 1756 KiB


2025-06-27 (Fri)
04:01:53 +09:00