Submission #70743843

Source Code Expand

Copy
#include <stdio.h>
#define MOD_BY1 392641980614146831ULL
#define MULT1 170590990642564171ULL
#define MOD_BY2 753631600352990131ULL
#define MULT2 521738074042690103ULL
typedef unsigned long long ull;
ull add(ull a, ull b, ull m) {
  return a + b - m * (a + b >= m);
}
ull sub(ull a, ull b, ull m) {
  return b == 0 ? a : add(a, m - b, m);
}
ull mul(ull a, ull b, ull m) {
  return (ull)((__int128)a * b % m);
}
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include <stdio.h>

#define MOD_BY1 392641980614146831ULL
#define MULT1 170590990642564171ULL
#define MOD_BY2 753631600352990131ULL
#define MULT2 521738074042690103ULL

typedef unsigned long long ull;

ull add(ull a, ull b, ull m) {
	return a + b - m * (a + b >= m);
}

ull sub(ull a, ull b, ull m) {
	return b == 0 ? a : add(a, m - b, m);
}

ull mul(ull a, ull b, ull m) {
	return (ull)((__int128)a * b % m);
}

ull pou(ull a, ull b, ull m) {
	ull r = 1;
	while (b > 0) {
		if (b & 1) r = mul(r, a, m);
		a = mul(a, a, m);
		b >>= 1;
	}
	return r;
}

ull inv(ull a, ull m) {
	return pou(a, m - 2, m);
}

#define MAX 1123456

ull pous1[MAX], pous2[MAX];
ull invs1[MAX], invs2[MAX];

char A[MAX];
char B[MAX];
ull ahash1[MAX], ahash2[MAX], bhash1[MAX], bhash2[MAX];

int main(void) {
	int T, tc;
	int i;
	pous1[0] = pous2[0] = invs1[0] = invs2[0] = 1;
	pous1[1] = MULT1;
	pous2[1] = MULT2;
	invs1[1] = inv(MULT1, MOD_BY1);
	invs2[1] = inv(MULT2, MOD_BY2);
	for (i = 2; i < MAX; i++) {
		pous1[i] = mul(pous1[i - 1], MULT1, MOD_BY1);
		pous2[i] = mul(pous2[i - 1], MULT2, MOD_BY2);
		invs1[i] = mul(invs1[i - 1], invs1[1], MOD_BY1);
		invs2[i] = mul(invs2[i - 1], invs2[1], MOD_BY2);
	}
	if (scanf("%d", &T) != 1) return 1;
	for (tc = 0; tc < T; tc++) {
		int len;
		if (scanf("%1123455s", A) != 1) return 1;
		if (scanf("%1123455s", B) != 1) return 1;
		ahash1[0] = ahash2[0] = (unsigned char)A[0];
		bhash1[0] = bhash2[0] = (unsigned char)B[0];
		for (i = 1; A[i] != '\0'; i++) {
			ahash1[i] = add(ahash1[i - 1], mul((unsigned char)A[i], pous1[i], MOD_BY1), MOD_BY1);
			ahash2[i] = add(ahash2[i - 1], mul((unsigned char)A[i], pous2[i], MOD_BY2), MOD_BY2);
			bhash1[i] = add(bhash1[i - 1], mul((unsigned char)B[i], pous1[i], MOD_BY1), MOD_BY1);
			bhash2[i] = add(bhash2[i - 1], mul((unsigned char)B[i], pous2[i], MOD_BY2), MOD_BY2);
		}
		len = i;
		if (ahash1[len - 1] == bhash1[len - 1] && ahash2[len - 1] == bhash2[len - 1]) {
			puts("0");
		} else {
			for (i = 1; i < len; i++) {
				ull ahashl1 = ahash1[i - 1];
				ull ahashl2 = ahash2[i - 1];
				ull ahashr1 = mul(sub(ahash1[len - 1], ahash1[i - 1], MOD_BY1), invs1[i], MOD_BY1);
				ull ahashr2 = mul(sub(ahash2[len - 1], ahash2[i - 1], MOD_BY2), invs2[i], MOD_BY2);
				ull bhashl1 = bhash1[len - 1 - i];
				ull bhashl2 = bhash2[len - 1 - i];
				ull bhashr1 = mul(sub(bhash1[len - 1], bhash1[len - 1 - i], MOD_BY1), invs1[len - i], MOD_BY1);
				ull bhashr2 = mul(sub(bhash2[len - 1], bhash2[len - 1 - i], MOD_BY2), invs2[len - i], MOD_BY2);
				if (ahashl1 == bhashr1 && ahashl2 == bhashr2 && ahashr1 == bhashl1 && ahashr2 == bhashl2) {
					printf("%d\n", i);
					break;
				}
			}
			if (i >= len) puts("-1");
		}
	}
	return 0;
}

Submission Info

Submission Time
Task E - Shift String
User mikecat
Language C23 (GCC 14.2.0)
Score 450
Code Size 2795 Byte
Status AC
Exec Time 61 ms
Memory 70108 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 450 / 450
Status
AC × 1
AC × 52
Set Name Test Cases
Sample sample_01.txt
All killer_01.txt, sample_01.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, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt, test_48.txt, test_49.txt, test_50.txt
Case Name Status Exec Time Memory
killer_01.txt AC 37 ms 36764 KiB
sample_01.txt AC 24 ms 36892 KiB
test_01.txt AC 24 ms 36844 KiB
test_02.txt AC 24 ms 36832 KiB
test_03.txt AC 23 ms 36896 KiB
test_04.txt AC 23 ms 36832 KiB
test_05.txt AC 24 ms 36832 KiB
test_06.txt AC 26 ms 36896 KiB
test_07.txt AC 26 ms 36836 KiB
test_08.txt AC 46 ms 36832 KiB
test_09.txt AC 46 ms 36780 KiB
test_10.txt AC 45 ms 36892 KiB
test_11.txt AC 44 ms 36792 KiB
test_12.txt AC 45 ms 37092 KiB
test_13.txt AC 45 ms 37088 KiB
test_14.txt AC 47 ms 40220 KiB
test_15.txt AC 47 ms 40120 KiB
test_16.txt AC 57 ms 69980 KiB
test_17.txt AC 56 ms 69996 KiB
test_18.txt AC 48 ms 69992 KiB
test_19.txt AC 49 ms 69992 KiB
test_20.txt AC 51 ms 70008 KiB
test_21.txt AC 51 ms 70048 KiB
test_22.txt AC 50 ms 70048 KiB
test_23.txt AC 50 ms 70108 KiB
test_24.txt AC 49 ms 70008 KiB
test_25.txt AC 50 ms 70044 KiB
test_26.txt AC 50 ms 69984 KiB
test_27.txt AC 53 ms 69972 KiB
test_28.txt AC 59 ms 69876 KiB
test_29.txt AC 60 ms 69988 KiB
test_30.txt AC 58 ms 69980 KiB
test_31.txt AC 59 ms 70004 KiB
test_32.txt AC 59 ms 69996 KiB
test_33.txt AC 61 ms 69992 KiB
test_34.txt AC 60 ms 69880 KiB
test_35.txt AC 56 ms 69944 KiB
test_36.txt AC 58 ms 69916 KiB
test_37.txt AC 58 ms 69996 KiB
test_38.txt AC 59 ms 69876 KiB
test_39.txt AC 59 ms 69952 KiB
test_40.txt AC 61 ms 69916 KiB
test_41.txt AC 58 ms 69952 KiB
test_42.txt AC 58 ms 69920 KiB
test_43.txt AC 50 ms 69988 KiB
test_44.txt AC 58 ms 70044 KiB
test_45.txt AC 59 ms 69844 KiB
test_46.txt AC 59 ms 69964 KiB
test_47.txt AC 28 ms 36892 KiB
test_48.txt AC 28 ms 36792 KiB
test_49.txt AC 58 ms 70048 KiB
test_50.txt AC 57 ms 69952 KiB
Facebook Twitter Telegram Share

2025-11-08 (Sat)
08:15:02 +09:00

More…