Submission #409439

#	Time	Username	Problem	Language	Result	Execution time	Memory
409439		rainboy	Languages (IOI10_languages)	C11	100 / 100	6720 ms	11212 KiB

lang

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

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

typedef unsigned long long ull;

unsigned int X = 12345;

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

void sort(ull *aa, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r;
		ull 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(ull *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(ull *aa, int n, ull *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_;

ull *merge(ull *aa, int n, ull *bb, int m) {
	static ull 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 = (ull *) realloc(aa, n * 2 * sizeof *aa);
		n++;
	}
	memcpy(aa, cc, n * sizeof *cc);
	return aa;
}

void excerpt(int *E) {
	static ull *aaa[L], *bbb[L], *ccc[L], *ddd[L], aa[N], bb[N], cc[N], dd[N];
	static int nn1[L], nn2[L], nn3[L], nn4[L];
	int n1, n2, n3, n4, i, l, l_, score_;

	for (i = 0; i < N; i++)
		aa[i] = E[i];
	for (i = 0; i < N - 1; i++)
		bb[i] = (ull) E[i] << 16 | E[i + 1];
	for (i = 0; i < N - 2; i++)
		cc[i] = ((ull) E[i] << 16 | E[i + 1]) << 16 | E[i + 2];
	for (i = 0; i < N - 3; i++)
		dd[i] = (((ull) E[i] << 16 | E[i + 1]) << 16 | E[i + 2]) << 16 | E[i + 3];
	n1 = process(aa, N), n2 = process(bb, N - 1), n3 = process(cc, N - 2), n4 = process(dd, N - 3);
	score_ = -1, l_ = -1;
	for (l = 0; l < L; l++) {
		int score = count(aaa[l], nn1[l], aa, n1) * 10 + count(bbb[l], nn2[l], bb, n2) * 6 + count(ccc[l], nn3[l], cc, n3) * 6 + count(ddd[l], nn4[l], dd, n4) * 12;

		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_;
	ccc[l_] = merge(ccc[l_], nn3[l_], cc, n3), nn3[l_] = n_;
	ddd[l_] = merge(ddd[l_], nn4[l_], dd, n4), nn4[l_] = n_;
}

Compilation message (stderr)

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

• Subtask 1: 30 / 30
• Subtask 2: 70 / 80