(cache)Submission #74793959 - AtCoder Beginner Contest 439

Contest Duration: 2026-01-03(Sat) 21:00 - 2026-01-03(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #74793959

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
int cmp(const void* x, const void* y) {
  int a = *(const int*)x, b = *(const int*)y;
  return (a > b) - (a < b);
}
int zac;
int zal[312345];
int zaq(int q) {
  int l = 0, r = zac - 1;
  while (l <= r) {
    int m = l + (r - l) / 2;
    if (zal[m] == q) return m;
    else if (zal[m] < q) l = m + 1;
    else r = m - 1;
  }
  return -1;
}
int N;
int A[312345];
int cnt_left[312345], cnt_right[312345];
int main(void) {
  int i;
  int64_t ans = 0;
  if (scanf("%d", &N) != 1) return 1;
  for (i = 0; i < N; i++) {
    if (scanf("%d", &A[i]) != 1) return 1;
  }
  memcpy(zal, A, sizeof(*A) * N);
  qsort(zal, N, sizeof(*zal), cmp);
  for (zac = 1, i = 1; i < N; i++) {
    if (zal[i] != zal[zac - 1]) zal[zac++] = zal[i];
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return (a > b) - (a < b);
}

int zac;
int zal[312345];

int zaq(int q) {
	int l = 0, r = zac - 1;
	while (l <= r) {
		int m = l + (r - l) / 2;
		if (zal[m] == q) return m;
		else if (zal[m] < q) l = m + 1;
		else r = m - 1;
	}
	return -1;
}

int N;
int A[312345];

int cnt_left[312345], cnt_right[312345];

int main(void) {
	int i;
	int64_t ans = 0;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
	}
	memcpy(zal, A, sizeof(*A) * N);
	qsort(zal, N, sizeof(*zal), cmp);
	for (zac = 1, i = 1; i < N; i++) {
		if (zal[i] != zal[zac - 1]) zal[zac++] = zal[i];
	}
	for (i = 0; i < N; i++) {
		int64_t long_a = (int64_t)A[i];
		int64_t nana, san;
		int cur_idx, nana_idx, san_idx;
		cur_idx = zaq(A[i]);
		if (cur_idx < 0) continue;
		cnt_left[cur_idx]++;
		if (long_a * 7 % 5 != 0 || long_a * 3 % 5 != 0) continue;
		nana = long_a * 7 / 5;
		san = long_a * 3 / 5;
		if (nana > zal[zac - 1]) continue;
		nana_idx = zaq((int)nana);
		san_idx = zaq((int)san);
		if (nana_idx < 0 || san_idx < 0) continue;
		ans += (int64_t)cnt_left[nana_idx] * cnt_left[san_idx];
	}
	for (i = N - 1; i >= 0; i--) {
		int64_t long_a = (int64_t)A[i];
		int64_t nana, san;
		int cur_idx, nana_idx, san_idx;
		cur_idx = zaq(A[i]);
		if (cur_idx < 0) continue;
		cnt_right[cur_idx]++;
		if (long_a * 7 % 5 != 0 || long_a * 3 % 5 != 0) continue;
		nana = long_a * 7 / 5;
		san = long_a * 3 / 5;
		if (nana > zal[zac - 1]) continue;
		nana_idx = zaq((int)nana);
		san_idx = zaq((int)san);
		if (nana_idx < 0 || san_idx < 0) continue;
		ans += (int64_t)cnt_right[nana_idx] * cnt_right[san_idx];
	}
	printf("%" PRId64 "\n", ans);
	return 0;
}

Submission Info

Submission Time	2026-04-10 00:42:10
Task	D - Kadomatsu Subsequence
User	mikecat
Language	C23 (GCC 14.2.0)
Score	425
Code Size	1910 Byte
Status	AC
Exec Time	196 ms
Memory	6484 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

425 / 425

Status

× 3

× 33

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

Case Name	Status	Exec Time	Memory
sample_01.txt	AC	0 ms	1684 KiB
sample_02.txt	AC	0 ms	1676 KiB
sample_03.txt	AC	0 ms	1684 KiB
test_01.txt	AC	0 ms	1644 KiB
test_02.txt	AC	0 ms	1648 KiB
test_03.txt	AC	0 ms	1652 KiB
test_04.txt	AC	0 ms	1676 KiB
test_05.txt	AC	28 ms	4532 KiB
test_06.txt	AC	28 ms	4820 KiB
test_07.txt	AC	28 ms	4712 KiB
test_08.txt	AC	29 ms	4900 KiB
test_09.txt	AC	29 ms	5096 KiB
test_10.txt	AC	29 ms	5156 KiB
test_11.txt	AC	34 ms	4720 KiB
test_12.txt	AC	39 ms	5108 KiB
test_13.txt	AC	35 ms	5020 KiB
test_14.txt	AC	41 ms	4872 KiB
test_15.txt	AC	44 ms	5108 KiB
test_16.txt	AC	43 ms	5104 KiB
test_17.txt	AC	57 ms	5116 KiB
test_18.txt	AC	75 ms	5096 KiB
test_19.txt	AC	68 ms	5068 KiB
test_20.txt	AC	137 ms	5112 KiB
test_21.txt	AC	102 ms	5112 KiB
test_22.txt	AC	125 ms	5148 KiB
test_23.txt	AC	196 ms	5104 KiB
test_24.txt	AC	191 ms	5064 KiB
test_25.txt	AC	136 ms	5100 KiB
test_26.txt	AC	136 ms	6484 KiB
test_27.txt	AC	135 ms	6400 KiB
test_28.txt	AC	137 ms	6440 KiB
test_29.txt	AC	136 ms	6464 KiB
test_30.txt	AC	138 ms	6432 KiB