Submission #409432

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
409432	2021-05-20T17:48:38 Z	rainboy	Languages (IOI10_languages)	C	82 / 100	1404 ms	1884 KB

lang

#include <stdlib.h>
#include <string.h>
#include "grader.h"
#include "lang.h"

#define N	100
#define N_	1000000
#define L	56

unsigned int X = 12345;

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

void sort(long long *aa, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r;
		long long a = aa[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (aa[j] == a)
				j++;
			else if (aa[j] < a) {
				tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = aa[j], aa[j] = aa[k], aa[k] = tmp;
			}
		sort(aa, l, i);
		l = k;
	}
}

int process(long long *aa, int n) {
	int n_, i;

	sort(aa, 0, n);
	n_ = 0;
	for (i = 0; i < n; i++)
		if (n_ == 0 || aa[i] != aa[n_ - 1])
			aa[n_++] = aa[i];
	return n_;
}

int count(long long *aa, int n, long long *bb, int m) {
	int i, j, k;

	i = 0, j = 0, k = 0;
	while (i < n && j < m)
		if (aa[i] == bb[j])
			i++, j++, k++;
		else if (aa[i] < bb[j])
			i++;
		else
			j++;
	return k;
}

int n_;

long long *merge(long long *aa, int n, long long *bb, int m) {
	static long long cc[N_];
	int i, j;

	i = 0, j = 0, n_ = 0;
	while (i < n && j < m)
		if (aa[i] == bb[j])
			cc[n_++] = aa[i], i++, j++;
		else if (aa[i] < bb[j])
			cc[n_++] = aa[i++];
		else
			cc[n_++] = bb[j++];
	while (i < n)
		cc[n_++] = aa[i++];
	while (j < m)
		cc[n_++] = bb[j++];
	while (n < n_) {
		if (n == 0)
			aa = malloc(2 * sizeof *aa);
		else if (n >= 2 && (n & n - 1) == 0)
			aa = (long long *) realloc(aa, n * 2 * sizeof *aa);
		n++;
	}
	memcpy(aa, cc, n * sizeof *cc);
	return aa;
}

void excerpt(int *E) {
	static long long *aaa[L], *bbb[L], aa[N], bb[N];
	static int nn1[L], nn2[L];
	int n1, n2, i, l, l_, score_;

	for (i = 0; i < N; i++)
		aa[i] = E[i];
	for (i = 0; i < N - 1; i++)
		bb[i] = (long long) E[i] << 16 | E[i + 1];
	n1 = process(aa, N), n2 = process(bb, N - 1);
	score_ = -1, l_ = -1;
	for (l = 0; l < L; l++) {
		int score = count(aaa[l], nn1[l], aa, n1) + count(bbb[l], nn2[l], bb, n2) * 5;

		if (score_ < score)
			score_ = score, l_ = l;
	}
	l_ = language(l_);
	aaa[l_] = merge(aaa[l_], nn1[l_], aa, n1), nn1[l_] = n_;
	bbb[l_] = merge(bbb[l_], nn2[l_], bb, n2), nn2[l_] = n_;
}

Compilation message

lang.c: In function 'merge':
lang.c:82:29: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   82 |   else if (n >= 2 && (n & n - 1) == 0)
      |                           ~~^~~

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1404 ms	1704 KB	Output is correct

Subtask #2

52.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	1397 ms	1884 KB	Output is partially correct - 75.19%