oj.uz

Submission #1099872

# Submission time Handle Problem Language Result Execution time Memory
1099872 2024-10-12T05:40:33 Z model_code Hieroglyphs (IOI24_hieroglyphs) C++17
0 / 100
 847 ms 2097152 KB 
// time_limit/agustin-heuristic.cpp

//#include "hieroglyphs.h"
#include <iostream>
#include <vector>

using namespace std;

#define forn(i,n) for (int i=0;i<int(n);i++)
#define dforn(i,n) for (int i=int(n)-1;i>=0;i--)
#define SIZE(c) int((c).size())

const int MAX_NUM = 200000;

vector<int> aIndex[MAX_NUM];
vector<int> bIndex[MAX_NUM];

vector<int> lcs(const vector<int> &A, const vector<int> &B, bool maximizing)
{
	const int N = SIZE(A);
	const int M = SIZE(B);
	vector<vector<int>> dp(N+1, vector<int>(M+1));
	forn(j,M+1)
		dp[0][j] = 0;
	forn(i,N+1)
		dp[i][0] = 0;
	dforn(i,N)
	dforn(j,M)
	if (A[i] == B[j])
		dp[i][j] = 1 + dp[i+1][j+1];
	else
		dp[i][j] = max(dp[i][j+1], dp[i+1][j]);
	vector<int> ret;
	int i = 0, j = 0;
	while (dp[i][j] > 0)
	{
		if (A[i] == B[j])
		{
			ret.push_back(A[i]);
			i++;
			j++;
		}
		else if (dp[i+1][j] < dp[i][j+1])
			j++;
		else if (dp[i+1][j] > dp[i][j+1])
			i++;
		else if ((A[i] < B[j]) != maximizing)
			j++;
		else
			i++;
	}
	return ret;
}

vector<int> ucs(vector<int> A, vector<int> B) {
  vector<int> v1 = lcs(A,B,false);
  vector<int> v2 = lcs(A,B,true);
  if (v1 == v2)
	return v1;
  else
    return {-1};
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 6 ms 13804 KB Output is correct
4 Correct 6 ms 13660 KB Output is correct
5 Runtime error 843 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 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 6 ms 13804 KB Output is correct
4 Correct 6 ms 13660 KB Output is correct
5 Runtime error 843 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 847 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 847 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 2 ms 10072 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Incorrect 2 ms 9820 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 2 ms 9816 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 6 ms 13804 KB Output is correct
7 Correct 6 ms 13660 KB Output is correct
8 Runtime error 843 ms 2097152 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -