Submission #68243484

Source Code Expand

Copy
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int N;
char s[51234][24];
int a[51234];
int M;
char type[21234];
char t[21234][24];
int b[21234];
int cmp_cp(const void* x, const void* y) {
  return strcmp(*(const char**)x, *(const char**)y);
}
int zac;
char* zal[51234 + 21234];
int zaq(const char* q) {
  int l = 0, r = zac - 1;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int N;
char s[51234][24];
int a[51234];
int M;
char type[21234];
char t[21234][24];
int b[21234];

int cmp_cp(const void* x, const void* y) {
	return strcmp(*(const char**)x, *(const char**)y);
}

int zac;
char* zal[51234 + 21234];

int zaq(const char* q) {
	int l = 0, r = zac - 1;
	while (l <= r) {
		int m = l + (r - l) / 2;
		int c = strcmp(zal[m], q);
		if (c == 0) return m;
		else if (c < 0) l = m + 1;
		else r = m - 1;
	}
	printf("ERROR: %s not found!\n", q);
	exit(42);
}

struct member_s {
	int name_id;
	long long motivation;
};

struct pq_s {
	struct member_s members[51234 + 21234];
	int member_cnt;
	int smaller_first;
};

void pq_adjust(struct pq_s* pq, int idx) {
	for (;;) {
		int min_idx = idx;
		int i;
		for (i = 1; i <= 2; i++) {
			int c = idx * 2 + i;
			if (
				c < pq->member_cnt && (
					pq->smaller_first
						? pq->members[c].motivation < pq->members[min_idx].motivation
						: pq->members[c].motivation > pq->members[min_idx].motivation
				)
			) min_idx = c;
		}
		if (min_idx == idx) {
			if (idx == 0) return;
			idx = (idx - 1) / 2;
		} else {
			struct member_s t = pq->members[idx];
			pq->members[idx] = pq->members[min_idx];
			pq->members[min_idx] = t;
			idx = min_idx;
		}
	}
}

void pq_add(struct pq_s* pq, int name_id, long long motivation) {
	pq->members[pq->member_cnt++] = (struct member_s){ name_id, motivation };
	pq_adjust(pq, pq->member_cnt - 1);
}

struct member_s pq_get(struct pq_s* pq) {
	struct member_s res;
	if (pq->member_cnt <= 0) {
		puts("ERROR: get from empty priority queue!");
		exit(72);
	}
	res = pq->members[0];
	if (--pq->member_cnt > 0) {
		pq->members[0] = pq->members[pq->member_cnt];
		pq_adjust(pq, 0);
	}
	return res;
}

struct pqd_s {
	struct pq_s main;
	struct pq_s deleted;
};

void pqd_add(struct pqd_s* pqd, int name_id, long long motivation) {
	pq_add(&pqd->main, name_id, motivation);
}

/* 削除対象は pqd にあると仮定する (無いと誤動作する) */
void pqd_delete(struct pqd_s* pqd, int name_id, long long motivation) {
	pq_add(&pqd->deleted, name_id, motivation);
}

/* 内部操作：deleted と main の両方にあることがわかるものを相殺する */
void pqd_cancel(struct pqd_s* pqd) {
	while (
		pqd->main.member_cnt > 0 && pqd->deleted.member_cnt > 0 &&
		pqd->main.members[0].name_id == pqd->deleted.members[0].name_id &&
		pqd->main.members[0].motivation == pqd->deleted.members[0].motivation
	) {
		pq_get(&pqd->main);
		pq_get(&pqd->deleted);
	}
}

int pqd_size(struct pqd_s* pqd) {
	return pqd->main.member_cnt - pqd->deleted.member_cnt;
}

struct member_s pqd_get(struct pqd_s* pqd) {
	pqd_cancel(pqd);
	return pq_get(&pqd->main);
}

struct member_s pqd_peek(struct pqd_s* pqd) {
	pqd_cancel(pqd);
	return pqd->main.members[0];
}

#define PLACE_NONE 0
#define PLACE_WORKHORSE 1
#define PLACE_IDLE_FELLOW 2

long long member_motivation[51234 + 21234];
int member_place[51234 + 21234];

struct pqd_s workhorse, idle_fellow;

int main(void) {
	int i;
	/* 初期化：下位グループは大きいもの (最上位) を出し、上位グループは小さいもの (最下位) を出す */
	workhorse.main.smaller_first = 1;
	workhorse.deleted.smaller_first = 1;

	/* 入力を読み込む */
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%23s%d", s[i], &a[i]) != 2) return 1;
	}
	if (scanf("%d", &M) != 1) return 1;
	for (i = 0; i < M; i++) {
		char buf[4];
		if (scanf("%3s%23s", buf, t[i]) != 2) return 1;
		type[i] = *buf;
		if (type[i] == '+') {
			if (scanf("%d", &b[i]) != 1) return 1;
		}
	}

	/* 名前にIDを割り当てる */
	for (i = 0; i < N; i++) zal[i] = s[i];
	for (i = 0; i < M; i++) zal[N + i] = t[i];
	qsort(zal, N + M, sizeof(*zal), cmp_cp);
	zac = 1;
	for (i = 1; i < N + M; i++) {
		if (strcmp(zal[zac - 1], zal[i]) != 0) zal[zac++] = zal[i];
	}

	/* 既存メンバーを下位グループに登録する */
	for (i = 0; i < N; i++) {
		int id = zaq(s[i]);
		member_motivation[id] = (long long)a[i] * 100000 + i;
		member_place[id] = PLACE_IDLE_FELLOW;
		pqd_add(&idle_fellow, id, member_motivation[id]);
	}
	/* 既存メンバーのうち上位のものを上位グループに移動する */
	for (i = 0; i < N / 5; i++) {
		struct member_s m = pqd_get(&idle_fellow);
		member_place[m.name_id] = PLACE_WORKHORSE;
		pqd_add(&workhorse, m.name_id, m.motivation);
	}

	/* クエリの処理を行う */
	for (i = 0; i < M; i++) {
		int all_cnt;
		/* メンバーの追加または削除を行う */
		int id = zaq(t[i]);
		if (type[i] == '+') {
			member_motivation[id] = (long long)b[i] * 100000 + N + i;
			if (pqd_size(&workhorse) > 0 && pqd_peek(&workhorse).motivation < member_motivation[id]) {
				/* 上位グループの最下位より上 → 上位グループ確定 */
				member_place[id] = PLACE_WORKHORSE;
			} else if (pqd_size(&idle_fellow) > 0 && pqd_peek(&idle_fellow).motivation > member_motivation[id]) {
				/* 下位グループの最上位より下 → 下位グループ確定 */
				member_place[id] = PLACE_IDLE_FELLOW;
			} else {
				/* 中間 → 数で判断 */
				int up_cnt = pqd_size(&workhorse);
				int low_cnt = pqd_size(&idle_fellow);
				int all_cnt = up_cnt + low_cnt + 1;
				member_place[id] = up_cnt < all_cnt / 5 ? PLACE_WORKHORSE : PLACE_IDLE_FELLOW;
			}
			if (member_place[id] == PLACE_WORKHORSE) {
				pqd_add(&workhorse, id, member_motivation[id]);
				printf("%s is working hard now.\n", zal[id]);
			} else {
				pqd_add(&idle_fellow, id, member_motivation[id]);
				printf("%s is not working now.\n", zal[id]);
			}
		} else if (type[i] == '-') {
			if (member_place[id] == PLACE_WORKHORSE) {
				pqd_delete(&workhorse, id, member_motivation[id]);
			} else if (member_place[id] == PLACE_IDLE_FELLOW) {
				pqd_delete(&idle_fellow, id, member_motivation[id]);
			}
			member_place[id] = PLACE_NONE;
		}
		/* メンバーの移動を行う */
		all_cnt = pqd_size(&workhorse) + pqd_size(&idle_fellow);
		while (pqd_size(&workhorse) < all_cnt / 5) {
			/* 上位グループのメンバー数が不足している → 下位グループから移動する */
			struct member_s m = pqd_get(&idle_fellow);
			pqd_add(&workhorse, m.name_id, m.motivation);
			member_place[m.name_id] = PLACE_WORKHORSE;
			printf("%s is working hard now.\n", zal[m.name_id]);
		}
		while (pqd_size(&workhorse) > all_cnt / 5) {
			/* 上位グループのメンバー数が過剰 → 下位グループへ移動する */
			struct member_s m = pqd_get(&workhorse);
			pqd_add(&idle_fellow, m.name_id, m.motivation);
			member_place[m.name_id] = PLACE_IDLE_FELLOW;
			printf("%s is not working now.\n", zal[m.name_id]);
		}
	}

	return 0;
}

Submission Info

Submission Time
Task C - We Don't Wanna Work!
User mikecat
Language C (gcc 12.2.0)
Score 100
Code Size 6943 Byte
Status AC
Exec Time 58 ms
Memory 6132 KiB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 66
Set Name Test Cases
All 0_sample_00, 0_sample_01, 0_sample_02, 0_sample_03, 0_sample_04, 1_small_0, 1_small_1, 1_small_2, 1_small_3, 1_small_4, 2_large_0, 2_large_1, 2_large_2, 2_large_3, 2_large_4, 3_random_0, 3_random_1, 3_random_2, 3_random_3, 3_random_4, 3_random_5, 3_random_6, 3_random_7, 3_random_8, 3_random_9, 4_random_0, 4_random_1, 4_random_2, 4_random_3, 4_random_4, 4_random_5, 4_random_6, 4_random_7, 4_random_8, 4_random_9, 5_random_0, 5_random_1, 5_random_2, 5_random_3, 5_random_4, 5_random_5, 5_random_6, 5_random_7, 5_random_8, 5_random_9, 6_random_0, 6_random_1, 6_random_2, 6_random_3, 6_random_4, 6_random_5, 6_random_6, 6_random_7, 6_random_8, 6_random_9, 7_random_0, 7_random_1, 7_random_2, 7_random_3, 7_random_4, 7_random_5, 7_random_6, 7_random_7, 7_random_8, 7_random_9, 9_killer_0
Case Name Status Exec Time Memory
0_sample_00 AC 1 ms 1704 KiB
0_sample_01 AC 1 ms 1640 KiB
0_sample_02 AC 1 ms 1648 KiB
0_sample_03 AC 1 ms 1756 KiB
0_sample_04 AC 1 ms 1704 KiB
1_small_0 AC 1 ms 1564 KiB
1_small_1 AC 1 ms 1732 KiB
1_small_2 AC 1 ms 1680 KiB
1_small_3 AC 1 ms 1732 KiB
1_small_4 AC 1 ms 1720 KiB
2_large_0 AC 58 ms 5988 KiB
2_large_1 AC 58 ms 6048 KiB
2_large_2 AC 58 ms 6132 KiB
2_large_3 AC 58 ms 6060 KiB
2_large_4 AC 58 ms 5920 KiB
3_random_0 AC 17 ms 3012 KiB
3_random_1 AC 36 ms 4412 KiB
3_random_2 AC 43 ms 5144 KiB
3_random_3 AC 24 ms 3616 KiB
3_random_4 AC 31 ms 4096 KiB
3_random_5 AC 49 ms 5484 KiB
3_random_6 AC 2 ms 1772 KiB
3_random_7 AC 41 ms 5096 KiB
3_random_8 AC 43 ms 5324 KiB
3_random_9 AC 31 ms 4256 KiB
4_random_0 AC 49 ms 5368 KiB
4_random_1 AC 20 ms 3380 KiB
4_random_2 AC 34 ms 4652 KiB
4_random_3 AC 10 ms 2588 KiB
4_random_4 AC 23 ms 3484 KiB
4_random_5 AC 17 ms 3260 KiB
4_random_6 AC 37 ms 4744 KiB
4_random_7 AC 3 ms 1920 KiB
4_random_8 AC 36 ms 4660 KiB
4_random_9 AC 24 ms 3608 KiB
5_random_0 AC 22 ms 3400 KiB
5_random_1 AC 35 ms 4716 KiB
5_random_2 AC 23 ms 3524 KiB
5_random_3 AC 43 ms 5256 KiB
5_random_4 AC 16 ms 2988 KiB
5_random_5 AC 28 ms 3624 KiB
5_random_6 AC 7 ms 2336 KiB
5_random_7 AC 20 ms 3396 KiB
5_random_8 AC 22 ms 3596 KiB
5_random_9 AC 16 ms 2904 KiB
6_random_0 AC 23 ms 3592 KiB
6_random_1 AC 40 ms 4792 KiB
6_random_2 AC 14 ms 2860 KiB
6_random_3 AC 9 ms 2520 KiB
6_random_4 AC 50 ms 5352 KiB
6_random_5 AC 33 ms 4280 KiB
6_random_6 AC 20 ms 3532 KiB
6_random_7 AC 36 ms 4848 KiB
6_random_8 AC 14 ms 2988 KiB
6_random_9 AC 21 ms 3380 KiB
7_random_0 AC 35 ms 4532 KiB
7_random_1 AC 28 ms 3844 KiB
7_random_2 AC 8 ms 2484 KiB
7_random_3 AC 31 ms 4488 KiB
7_random_4 AC 40 ms 4668 KiB
7_random_5 AC 50 ms 5376 KiB
7_random_6 AC 51 ms 5644 KiB
7_random_7 AC 38 ms 4712 KiB
7_random_8 AC 31 ms 4376 KiB
7_random_9 AC 36 ms 4672 KiB
9_killer_0 AC 1 ms 1680 KiB
Facebook Twitter Telegram Share

2025-08-06 (Wed)
08:42:02 +09:00

More…