Submission #1099868

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1099868	2024-10-12T05:39:57 Z	model_code	Hieroglyphs (IOI24_hieroglyphs)	C++17	0 / 100	806 ms	2097152 KB

hieroglyphs

// failed/author-quadratic.cpp

#include<bits/stdc++.h>
#include "hieroglyphs.h"

using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;


vi lcs(const vi& a, const vi& b) {
	int n = a.size();
	int m = b.size();

	vvi dp(n+1, vi(m+1));
	for (int i=1; i <= n; ++i) {
		for (int j=1; j <= m; ++j) {
			dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			if (a[i-1] == b[j-1]) dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1);
		}
	}

	vi c;
	int ci = n;
	int cj = m;
	while (ci > 0 && cj > 0) {
		if (a[ci-1] == b[cj-1] && dp[ci][cj] == dp[ci-1][cj-1]+1) {
			c.push_back(a[ci-1]);
			ci--;
			cj--;
		}
		else {
			if (dp[ci][cj] == dp[ci-1][cj]) {
				ci--;
			}
			else {
				cj--;
			}
		}
	}

	reverse(c.begin(), c.end());
	return c;
}

vector<int> ucs(vi a, vi b) {
	vi c = lcs(a, b);

	int n = a.size();
	int m = b.size();
	int l = c.size();

	vvi nxt(max(n, m)+1, vi(l+2, l)); //nxt[x][i] = first k such that c[k] = x and k >= i, l if such k does not exist

	for (int i=0; i < l; ++i) {
		for (int j=0; j <= i; ++j) {
			nxt[c[i]][j] = min(nxt[c[i]][j], i);
		}
	}

	vvi dp(n+1, vi(m+1, -1)); //dp[i][j] = maximum k so that there is a common subseq of a[0..i), b[0..j) which is not a subseq of c[0..k), -1 if no subseq

	for (int i=1; i <= n; ++i) {
		for (int j=1; j <= m; ++j) {
			if (a[i-1] == b[j-1]) {
				dp[i][j] = nxt[a[i-1]][dp[i-1][j-1]+1];
			}
			dp[i][j] = max(dp[i][j], max(dp[i-1][j], dp[i][j-1]));
		}
	}

	if(dp[n][m] == l) return vector<int>({-1});
	return c;
}

Subtask #0

0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct

Subtask #1

0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	6 ms	8280 KB	Output is correct
4	Correct	6 ms	8280 KB	Output is correct
5	Runtime error	787 ms	2097152 KB	Execution killed with signal 9
6	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	6 ms	8280 KB	Output is correct
4	Correct	6 ms	8280 KB	Output is correct
5	Runtime error	787 ms	2097152 KB	Execution killed with signal 9
6	Halted	0 ms	0 KB	-

Subtask #3

0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	806 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #4

0.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	806 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Runtime error	25 ms	35676 KB	Execution killed with signal 11
11	Halted	0 ms	0 KB	-

Subtask #6

0.0 / 42.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	6 ms	8280 KB	Output is correct
7	Correct	6 ms	8280 KB	Output is correct
8	Runtime error	787 ms	2097152 KB	Execution killed with signal 9
9	Halted	0 ms	0 KB	-