Submission #409426

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
409426	2021-05-20T17:42:41 Z	rainboy	Languages (IOI10_languages)	C	56 / 100	350 ms	5760 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], aa[N];
	static int kk1[L];
	int n, i, l, l_, l1, score_;

	for (i = 0; i < N; i++)
		aa[i] = E[i];
	n = process(aa, N);
	score_ = -1, l_ = -1;
	for (l = 0; l < L; l++) {
		int score = count(aaa[l], kk1[l], aa, n);

		if (score_ < score)
			score_ = score, l_ = l;
	}
	l1 = language(l_);
	aaa[l1] = merge(aaa[l1], kk1[l1], aa, n), kk1[l1] = 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	350 ms	5760 KB	Output is correct

Subtask #2

26.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	348 ms	5720 KB	Output is partially correct - 52.57%