(cache)Submission #69718263 - AtCoder Beginner Contest 424

Contest Duration: 2025-09-20(Sat) 21:00 - 2025-09-20(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #69718263

Source Code Expand

Copy

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>
struct meow {
  double length;
  long long num;
};
int qsize = 0;
struct meow q[114514];
void qadjust(int node) {
  for (;;) {
    int maxidx = node;
    int i;
    for (i = 1; i <= 2; i++) {
      int c = node * 2 + i;
      if (c < qsize && q[maxidx].length < q[c].length) maxidx = c;
    }
    if (maxidx == node) {
      if (node == 0) return;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

struct meow {
	double length;
	long long num;
};

int qsize = 0;
struct meow q[114514];

void qadjust(int node) {
	for (;;) {
		int maxidx = node;
		int i;
		for (i = 1; i <= 2; i++) {
			int c = node * 2 + i;
			if (c < qsize && q[maxidx].length < q[c].length) maxidx = c;
		}
		if (maxidx == node) {
			if (node == 0) return;
			node = (node - 1) / 2;
		} else {
			struct meow temp = q[node];
			q[node] = q[maxidx];
			q[maxidx] = temp;
			node = maxidx;
		}
	}
}

void qadd(double length, long long num) {
	q[qsize++] = (struct meow){ length, num };
	qadjust(qsize - 1);
}

struct meow qget(void) {
	struct meow res;
	if (qsize <= 0) exit(42);
	res = q[0];
	if (--qsize > 0) {
		q[0] = q[qsize];
		qadjust(0);
	}
	return res;
}

int N, K, X;
int A[114514];

int main(void) {
	int T, tc;
	if (scanf("%d", &T) != 1) return 1;
	for (tc = 0; tc < T; tc++) {
		int i;
		if (scanf("%d%d%d", &N, &K, &X) != 3) return 1;
		for (i = 0; i < N; i++) {
			if (scanf("%d", &A[i]) != 1) return 1;
		}

		qsize = 0;
		for (i = 0; i < N; i++) {
			qadd(A[i], 1);
		}
		while (K > 0) {
			struct meow top = qget();
			if (top.num <= K) {
				qadd(top.length / 2, top.num * 2);
				K -= top.num;
			} else {
				qadd(top.length / 2, K * 2);
				qadd(top.length, top.num - K);
				K = 0;
			}
		}
		while (X > 0) {
			struct meow top = qget();
			if (top.num < X) {
				X -= top.num;
			} else {
				printf("%.20f\n", top.length);
				break;
			}
		}
	}
	return 0;
}

/*

同じ長さの棒がいっぱいできる → まとめて処理する
32周くらいすれば、十分いっぱいできる
Nが大きいほどいっぱいできにくいが、制約から多分なんとかなる

*/

Submission Info

Submission Time	2025-09-29 07:58:33
Task	E - Cut in Half
User	mikecat
Language	C (gcc 12.2.0)
Score	475
Code Size	1812 Byte
Status	AC
Exec Time	312 ms
Memory	3736 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

475 / 475

Status

× 1

× 36

Set Name	Test Cases
Sample	sample_01.txt
All	random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, random_35.txt, sample_01.txt

Case Name	Status	Exec Time	Memory
random_01.txt	AC	308 ms	3628 KiB
random_02.txt	AC	185 ms	2844 KiB
random_03.txt	AC	276 ms	3644 KiB
random_04.txt	AC	180 ms	2864 KiB
random_05.txt	AC	312 ms	3660 KiB
random_06.txt	AC	243 ms	3288 KiB
random_07.txt	AC	275 ms	3516 KiB
random_08.txt	AC	240 ms	3340 KiB
random_09.txt	AC	254 ms	1728 KiB
random_10.txt	AC	245 ms	1804 KiB
random_11.txt	AC	237 ms	1644 KiB
random_12.txt	AC	230 ms	1708 KiB
random_13.txt	AC	253 ms	1720 KiB
random_14.txt	AC	246 ms	1720 KiB
random_15.txt	AC	239 ms	1800 KiB
random_16.txt	AC	227 ms	1648 KiB
random_17.txt	AC	183 ms	3580 KiB
random_18.txt	AC	184 ms	3660 KiB
random_19.txt	AC	183 ms	3736 KiB
random_20.txt	AC	182 ms	3576 KiB
random_21.txt	AC	182 ms	3684 KiB
random_22.txt	AC	183 ms	3624 KiB
random_23.txt	AC	161 ms	3640 KiB
random_24.txt	AC	156 ms	3672 KiB
random_25.txt	AC	160 ms	3580 KiB
random_26.txt	AC	156 ms	3620 KiB
random_27.txt	AC	159 ms	3660 KiB
random_28.txt	AC	151 ms	3596 KiB
random_29.txt	AC	214 ms	3672 KiB
random_30.txt	AC	203 ms	3680 KiB
random_31.txt	AC	12 ms	3520 KiB
random_32.txt	AC	0 ms	1668 KiB
random_33.txt	AC	49 ms	1712 KiB
random_34.txt	AC	49 ms	1684 KiB
random_35.txt	AC	52 ms	1692 KiB
sample_01.txt	AC	1 ms	1680 KiB