oj.uz

Submission #930943

# Submission time Handle Problem Language Result Execution time Memory
930943 2024-02-20T21:09:47 Z rainboy 구간 성분 (KOI15_interval) C
7 / 100
 323 ms 98356 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	1500
#define M	1500
#define M_	(N * N)
#define A	26
#define MD	0x7fffffff

int max(int a, int b) { return a > b ? a : b; }

int X = 123454321;

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int uu[A], vv[A];

void init() {
	int a;
	
	for (a = 0; a < A; a++) {
		uu[a] = rand_();
		vv[a] = rand_();
	}
}

long long *ek[M_]; int eo[M_];

int hash(long long k) {
	int x = k / MD, y = k % MD;

	return ((long long) x * X + y) % MD % M_;
}

void ht_add(long long k) {
	int h = hash(k), o;

	for (o = eo[h]; o--; )
		if (ek[h][o] == k)
			return;
	o = eo[h]++;
	if (o >= 2 && (o & o - 1) == 0)
		ek[h] = (long long *) realloc(ek[h], o * 2 * sizeof *ek[h]);
	ek[h][o] = k;
}

int ht_contains(long long k) {
	int h = hash(k), o;

	for (o = eo[h]; o--; )
		if (ek[h][o] == k)
			return 1;
	return 0;
}

int main() {
	static char aa[N + 1], bb[M + 1];
	int n, m, h, i, j, a, x, y, ans;

	init();
	scanf("%s%s", aa, bb), n = strlen(aa), m = strlen(bb);
	for (h = 0; h < M_; h++)
		ek[h] = (long long *) malloc(2 * sizeof *ek[h]);
	for (i = 0; i < n; i++) {
		x = y = 0;
		for (j = i; j < n; j++) {
			a = aa[j] - 'a';
			x = ((long long) x + uu[a]) % MD, y = ((long long) y + vv[a]) % MD;
			ht_add((long long) x * MD + y);
		}
	}
	ans = 0;
	for (i = 0; i < m; i++) {
		x = y = 0;
		for (j = i; j < m; j++) {
			a = bb[j] - 'a';
			x = ((long long) x + uu[a]) % MD, y = ((long long) y + vv[a]) % MD;
			if (ht_contains((long long) x * MD + y))
				ans = max(ans, j - i + 1);
		}
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message

interval.c: In function 'ht_add':
interval.c:47:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   47 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
interval.c: In function 'main':
interval.c:66:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |  scanf("%s%s", aa, bb), n = strlen(aa), m = strlen(bb);
      |  ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 89816 KB Output is correct
2 Correct 61 ms 92500 KB Output is correct
3 Correct 60 ms 91604 KB Output is correct
4 Correct 63 ms 96340 KB Output is correct
5 Correct 62 ms 96076 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 97112 KB Output is correct
2 Incorrect 76 ms 97108 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 97272 KB Output is correct
2 Incorrect 155 ms 97404 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 97264 KB Output is correct
2 Correct 313 ms 98356 KB Output is correct
3 Incorrect 323 ms 98228 KB Output isn't correct
4 Halted 0 ms 0 KB -