Submission #1101135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101135		rainboy	Hieroglyphs (IOI24_hieroglyphs)	C++17	100 / 100	80 ms	26968 KiB

hieroglyphs

/* upsolved after discussing with Benq */
#include "hieroglyphs.h"
#include <cstdlib>
#include <cstring>
#include <vector>

using namespace std;

typedef vector<int> vi;

const int N = 100000, M = 100000, A = 200000, INF = 0x3f3f3f3f;

int min(int a, int b) { return a < b ? a : b; }

int aa_[N], bb_[M], iia[N], jja[N], iib[M], jjb[M], iic[N], jjc[N], iic_[N], jjc_[N], nxt[N], n, m, n_, m_, l;
int *eia[A + 1], eoa[A + 1], *ejb[A + 1], eob[A + 1];
int hh[A + 1];

void append(int **ei, int *eo, int a, int i) {
	int o = eo[a]++;
	if (o >= 2 && (o & o - 1) == 0)
		ei[a] = (int *) realloc(ei[a], o * 2 * sizeof *ei[a]);
	ei[a][o] = i;
}

int prev(int **ei, int *eo, int a, int i) {
	int lower = -1, upper = eo[a];
	while (upper - lower > 1) {
		int o = (lower + upper) / 2;
		if (ei[a][o] < i)
			lower = o;
		else
			upper = o;
	}
	return lower == -1 ? -1 : ei[a][lower];
}

int next(int **ei, int *eo, int a, int i) {
	int lower = -1, upper = eo[a];
	while (upper - lower > 1) {
		int o = (lower + upper) / 2;
		if (ei[a][o] > i)
			upper = o;
		else
			lower = o;
	}
	return upper == eo[a] ? -1 : ei[a][upper];
}

int ft[N];

void update(int i, int n, int x) {
	while (i < n) {
		ft[i] = min(ft[i], x);
		i |= i + 1;
	}
}

int query(int i) {
	int x = INF;

	while (i >= 0) {
		x = min(x, ft[i]);
		i &= i + 1, i--;
	}
	return x;
}

vi ucs(vi aa, vi bb) {
	n = aa.size(), m = bb.size();
	for (int a = 0; a <= A; a++)
		eia[a] = (int *) malloc(2 * sizeof *eia[a]);
	for (int b = 0; b <= A; b++)
		ejb[b] = (int *) malloc(2 * sizeof *ejb[b]);
	for (int i = 0; i < n; i++)
		append(eia, eoa, aa[i], i);
	for (int j = 0; j < m; j++)
		append(ejb, eob, bb[j], j);
	for (int i = 0; i < n; i++) {
		int a = aa[i];
		if (eoa[a] <= eob[a])
			aa_[n_++] = a;
	}
	for (int j = 0; j < m; j++) {
		int b = bb[j];
		if (eoa[b] > eob[b])
			bb_[m_++] = b;
	}
	for (int i_ = 0, i = 0; i_ < n_; i_++) {
		while (i < n && aa[i] != aa_[i_])
			i++;
		iia[i_] = i++;
	}
	for (int i_ = 0, j = 0; i_ < n_; i_++) {
		while (j < m && bb[j] != aa_[i_])
			j++;
		if (j == m)
			return vi({ -1 });
		jja[i_] = j++;
	}
	for (int j_ = m_ - 1, i = n - 1; j_ >= 0; j_--) {
		while (i >= 0 && aa[i] != bb_[j_])
			i--;
		if (i < 0)
			return vi({ -1 });
		iib[j_] = i--;
	}
	for (int j_ = m_ - 1, j = m - 1; j_ >= 0; j_--) {
		while (j >= 0 && bb[j] != bb_[j_])
			j--;
		jjb[j_] = j--;
	}
	l = n_ + m_;
	vi cc(l);
	int h = 0, i_ = 0;
	for (int j_ = 0; j_ < m_; j_++) {
		while (i_ < n_ && iia[i_] < iib[j_] && jja[i_] < jjb[j_])
			cc[h++] = aa_[i_++];
		cc[h++] = bb_[j_];
	}
	while (i_ < n_)
		cc[h++] = aa_[i_++];
	for (int h = 0, i = 0; h < l; h++) {
		while (i < n && aa[i] != cc[h])
			i++;
		if (i == n)
			return vi({ -1 });
		iic[h] = i++;
	}
	for (int h = 0, j = 0; h < l; h++) {
		while (j < m && bb[j] != cc[h])
			j++;
		if (j == m)
			return vi({ -1 });
		jjc[h] = j++;
	}
	memset(hh, -1, (A + 1) * sizeof *hh);
	memset(ft, 0x3f, l * sizeof *ft);
	for (int h = 0; h < l; h++) {
		int c = cc[h], i = hh[c] == -1 ? -1 : query(l - 1 - hh[c]);
		hh[c] = h;
		update(l - 1 - h, l, iic_[h] = next(eia, eoa, c, i));
	}
	memset(hh, -1, (A + 1) * sizeof *hh);
	memset(ft, 0x3f, l * sizeof *ft);
	for (int h = 0; h < l; h++) {
		int c = cc[h], j = hh[c] == -1 ? -1 : query(l - 1 - hh[c]);
		hh[c] = h;
		update(l - 1 - h, l, jjc_[h] = next(ejb, eob, c, j));
	}
	memset(hh, -1, (A + 1) * sizeof *hh);
	for (int h = l - 1; h >= 0; h--) {
		int c = cc[h];
		nxt[h] = hh[c], hh[c] = h;
	}
	memset(ft, 0x3f, n * sizeof *ft);
	for (int c = 0; c <= A; c++) {
		int h = hh[c];
		if (h != -1) {
			int i = prev(eia, eoa, c, iic[h]), j = prev(ejb, eob, c, jjc[h]);
			if (i >= 0 && j >= 0)
				update(n - 1 - i, n, -j);
		}
	}
	for (int h = 0; h < l; h++) {
		int c = cc[h], q = nxt[h], i, j;
		if (q == -1)
			i = eia[c][eoa[c] - 1], j = ejb[c][eob[c] - 1];
		else
			i = prev(eia, eoa, c, iic[q]), j = prev(ejb, eob, c, jjc[q]);
		if (i >= 0 && j >= 0)
			update(n - 1 - i, n, -j);
		i = iic_[h], j = jjc[h];
		if (-query(n - 2 - i) > j)
			return vi({ -1 });
		i = iic[h], j = jjc_[h];
		if (-query(n - 2 - i) > j)
			return vi({ -1 });
	}
	return cc;
}

Compilation message (stderr)

hieroglyphs.cpp: In function 'void append(int**, int*, int, int)':
hieroglyphs.cpp:21:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   21 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 16 / 16
• Subtask 5: 14 / 14
• Subtask 6: 42 / 42