답안 #1099856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1099856	2024-10-12T05:37:48 Z	model_code	상형문자열 (IOI24_hieroglyphs)	C++17	43 / 100	230 ms	61608 KB

hieroglyphs

// incorrect/yiping-wa1.cpp

#include<bits/stdc++.h>
#include"hieroglyphs.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

struct Data
{
	int d;
	vector<int> a, cnt, rnk;
	vector< vector<int> > pos;
	
	Data(vector<int> _a, int _d)
	{
		a = _a; d = _d;
		cnt.resize(d); pos.resize(d); rnk.resize(a.size());
		for(int i=0; i<(int)a.size(); ++i)
		{
			int x = a[i];
			rnk[i] = cnt[x]; ++cnt[x];
			pos[x].emplace_back(i);
		}
	}
	bool check(int x,int cx,int y,int cy) const
	{
		if(cx > (int)pos[x].size() || cy > (int)pos[y].size())
			return 0;
		if(cx == 0 || cy == 0) return 1;
		return pos[x][cx - 1] < pos[y][(int)pos[y].size() - cy];
	}
	int get_next(int i,int x) const
	{
		auto it = lower_bound(pos[x].begin(), pos[x].end(), i);
		return it == pos[x].end()? (int)a.size(): *it;
	}
};

vector<int> get_cand(const Data &aa, const Data &bb)
{
	int d = aa.d;
	vector<int> type(d), need(d);
	for(int i=0; i<d; ++i)
	{
		type[i] = aa.cnt[i] <= bb.cnt[i]? 0: 1;
		need[i] = min(aa.cnt[i], bb.cnt[i]);
	}
	
	vector<pii> veca, vecb;
	for(int i=0; i<(int)aa.a.size(); ++i)
		if(type[aa.a[i]] == 0)
			veca.emplace_back(aa.a[i], aa.rnk[i]);
	for(int i=0; i<(int)bb.a.size(); ++i)
		if(type[bb.a[i]] == 1)
			vecb.emplace_back(bb.a[i], bb.rnk[i]);
	
	auto check = [&] (pii x,pii y)
	{
		return aa.check(x.first, x.second + 1, y.first, need[y.first] - y.second)
		    && bb.check(x.first, x.second + 1, y.first, need[y.first] - y.second);
	};
	
	vector<int> c;
	int i = 0, j = 0;
	while(i<(int)veca.size() && j<(int)vecb.size())
	{
		bool tx = check(veca[i], vecb[j]);
		bool ty = check(vecb[j], veca[i]);
		
		if(tx == ty) return {-1};
		
		if(tx) c.emplace_back(veca[i].first), ++i;
		else c.emplace_back(vecb[j].first), ++j;
	}
	
	while(i<(int)veca.size()) c.emplace_back(veca[i].first), ++i;
	while(j<(int)vecb.size()) c.emplace_back(vecb[j].first), ++j;
	
	return c;
}

bool is_invalid(const vector<int> &c)
{
	return c.size() == 1 && c[0] == -1;
}

bool is_subseq(const vector<int> &a, const vector<int> &c)
{
	int j = 0;
	for(int i=0; i<(int)a.size() && j<(int)c.size(); ++i)
		if(a[i] == c[j]) ++j;
	return j >= (int)c.size();
}

vector<int> ucs(vector<int> a, vector<int> b)
{
	int d = 0;
	for(auto t: a)
		d = max(d, t + 1);
	for(auto t: b)
		d = max(d, t + 1);
	
	Data aa(a, d), bb(b, d);
	
	auto c = get_cand(aa, bb);
	if(is_invalid(c)) return c;
	
	if(!is_subseq(a, c)) return {-1};
	if(!is_subseq(b, c)) return {-1};
	
	Data cc(c, d);
	
	const int LIM = 3000;
	const int pa = min(LIM, (int)a.size());
	const int pb = min(LIM, (int)b.size());
	
	int len_a = 0, len_b = 0;
	for(int i=(int)a.size()-1; i>=pa; --i)
		if(len_a < (int)c.size() && a[i] == c[(int)c.size() - len_a - 1])
			++len_a;
	for(int i=(int)b.size()-1; i>=pb; --i)
		if(len_b < (int)c.size() && b[i] == c[(int)c.size() - len_b - 1])
			++len_b;
	
	vector< vector<int> > dp(pa+1, vector<int>(pb+1));
	
	for(int i=0; i<=pa; ++i)
		for(int j=0; j<=pb; ++j)
		{
			if(i) dp[i][j] = max(dp[i][j], dp[i-1][j]);
			if(j) dp[i][j] = max(dp[i][j], dp[i][j-1]);
			if(i && j && a[i-1] == b[j-1])
			{
				dp[i][j] = max(dp[i][j], cc.get_next(dp[i-1][j-1], a[i-1]) + 1);
				if(dp[i][j] + min(len_a, len_b) > (int)c.size())
					return {-1};
			}
		}
	return c;
}

Subtask #0

0.0 / 0.0

#	결과	실행 시간	메모리	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

3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	4 ms	4444 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	93 ms	57644 KB	Output is correct
6	Correct	33 ms	17612 KB	Output is correct
7	Correct	34 ms	17612 KB	Output is correct

Subtask #2

0.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	4 ms	4444 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	93 ms	57644 KB	Output is correct
6	Correct	33 ms	17612 KB	Output is correct
7	Correct	34 ms	17612 KB	Output is correct
8	Correct	85 ms	61392 KB	Output is correct
9	Correct	87 ms	61392 KB	Output is correct
10	Correct	88 ms	61392 KB	Output is correct
11	Correct	83 ms	61256 KB	Output is correct
12	Correct	86 ms	61408 KB	Output is correct
13	Correct	85 ms	61396 KB	Output is correct
14	Correct	87 ms	61392 KB	Output is correct
15	Correct	87 ms	61392 KB	Output is correct
16	Correct	89 ms	61400 KB	Output is correct
17	Correct	92 ms	61392 KB	Output is correct
18	Correct	6 ms	16704 KB	Output is correct
19	Correct	6 ms	16468 KB	Output is correct
20	Correct	10 ms	18896 KB	Output is correct
21	Correct	23 ms	31548 KB	Output is correct
22	Correct	69 ms	57812 KB	Output is correct
23	Correct	90 ms	61464 KB	Output is correct
24	Correct	90 ms	61480 KB	Output is correct
25	Correct	80 ms	61608 KB	Output is correct
26	Correct	77 ms	58620 KB	Output is correct
27	Correct	86 ms	61172 KB	Output is correct
28	Correct	97 ms	61392 KB	Output is correct
29	Correct	34 ms	20464 KB	Output is correct
30	Correct	47 ms	20464 KB	Output is correct
31	Correct	95 ms	61412 KB	Output is correct
32	Incorrect	86 ms	61396 KB	Output isn't correct
33	Halted	0 ms	0 KB	-

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	174 ms	41320 KB	Output is correct
2	Correct	184 ms	41316 KB	Output is correct
3	Correct	113 ms	40512 KB	Output is correct
4	Correct	112 ms	40384 KB	Output is correct
5	Correct	209 ms	40844 KB	Output is correct
6	Correct	125 ms	37956 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	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	178 ms	41120 KB	Output is correct
17	Correct	14 ms	6220 KB	Output is correct
18	Correct	167 ms	39500 KB	Output is correct
19	Correct	11 ms	4164 KB	Output is correct
20	Correct	114 ms	40128 KB	Output is correct
21	Correct	15 ms	4664 KB	Output is correct
22	Correct	14 ms	6148 KB	Output is correct
23	Correct	13 ms	5696 KB	Output is correct
24	Correct	14 ms	5712 KB	Output is correct
25	Correct	13 ms	6076 KB	Output is correct
26	Correct	15 ms	5712 KB	Output is correct

Subtask #4

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	85 ms	61392 KB	Output is correct
2	Correct	87 ms	61392 KB	Output is correct
3	Correct	88 ms	61392 KB	Output is correct
4	Correct	83 ms	61256 KB	Output is correct
5	Correct	86 ms	61408 KB	Output is correct
6	Correct	85 ms	61396 KB	Output is correct
7	Correct	87 ms	61392 KB	Output is correct
8	Correct	87 ms	61392 KB	Output is correct
9	Correct	89 ms	61400 KB	Output is correct
10	Correct	92 ms	61392 KB	Output is correct
11	Correct	6 ms	16704 KB	Output is correct
12	Correct	6 ms	16468 KB	Output is correct
13	Correct	10 ms	18896 KB	Output is correct
14	Correct	23 ms	31548 KB	Output is correct
15	Correct	69 ms	57812 KB	Output is correct
16	Correct	90 ms	61464 KB	Output is correct
17	Correct	90 ms	61480 KB	Output is correct
18	Correct	80 ms	61608 KB	Output is correct
19	Correct	77 ms	58620 KB	Output is correct
20	Correct	174 ms	41320 KB	Output is correct
21	Correct	184 ms	41316 KB	Output is correct
22	Correct	113 ms	40512 KB	Output is correct
23	Correct	112 ms	40384 KB	Output is correct
24	Correct	209 ms	40844 KB	Output is correct
25	Correct	125 ms	37956 KB	Output is correct
26	Correct	47 ms	52092 KB	Output is correct
27	Correct	45 ms	52112 KB	Output is correct
28	Correct	41 ms	50412 KB	Output is correct
29	Correct	46 ms	51464 KB	Output is correct
30	Correct	10 ms	20808 KB	Output is correct
31	Correct	48 ms	48568 KB	Output is correct
32	Correct	46 ms	48960 KB	Output is correct
33	Correct	33 ms	42044 KB	Output is correct
34	Correct	65 ms	52988 KB	Output is correct
35	Correct	118 ms	57492 KB	Output is correct
36	Correct	91 ms	58124 KB	Output is correct
37	Correct	70 ms	58272 KB	Output is correct
38	Correct	207 ms	57768 KB	Output is correct
39	Correct	230 ms	57772 KB	Output is correct
40	Correct	102 ms	60120 KB	Output is correct
41	Correct	84 ms	58584 KB	Output is correct
42	Correct	70 ms	51480 KB	Output is correct
43	Correct	68 ms	52984 KB	Output is correct
44	Correct	62 ms	52796 KB	Output is correct
45	Correct	58 ms	51452 KB	Output is correct
46	Correct	79 ms	58992 KB	Output is correct
47	Correct	86 ms	59176 KB	Output is correct
48	Correct	76 ms	58780 KB	Output is correct
49	Correct	79 ms	58584 KB	Output is correct
50	Correct	78 ms	58584 KB	Output is correct
51	Correct	92 ms	58588 KB	Output is correct
52	Correct	78 ms	58576 KB	Output is correct
53	Correct	75 ms	58624 KB	Output is correct
54	Correct	79 ms	58484 KB	Output is correct
55	Correct	29 ms	22484 KB	Output is correct
56	Correct	71 ms	57936 KB	Output is correct
57	Correct	73 ms	57632 KB	Output is correct
58	Correct	87 ms	58380 KB	Output is correct
59	Correct	75 ms	57988 KB	Output is correct
60	Correct	89 ms	58324 KB	Output is correct

Subtask #5

14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 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	1 ms	348 KB	Output is correct
10	Correct	47 ms	52092 KB	Output is correct
11	Correct	45 ms	52112 KB	Output is correct
12	Correct	41 ms	50412 KB	Output is correct
13	Correct	46 ms	51464 KB	Output is correct
14	Correct	10 ms	20808 KB	Output is correct
15	Correct	48 ms	48568 KB	Output is correct
16	Correct	46 ms	48960 KB	Output is correct
17	Correct	33 ms	42044 KB	Output is correct
18	Correct	40 ms	33624 KB	Output is correct
19	Correct	43 ms	35932 KB	Output is correct
20	Correct	50 ms	36180 KB	Output is correct
21	Correct	43 ms	36188 KB	Output is correct
22	Correct	35 ms	33628 KB	Output is correct
23	Correct	46 ms	32860 KB	Output is correct
24	Correct	37 ms	35932 KB	Output is correct
25	Correct	21 ms	36180 KB	Output is correct
26	Correct	28 ms	36044 KB	Output is correct
27	Correct	30 ms	40512 KB	Output is correct
28	Correct	62 ms	52472 KB	Output is correct
29	Correct	51 ms	52292 KB	Output is correct
30	Correct	50 ms	52032 KB	Output is correct
31	Correct	53 ms	51820 KB	Output is correct
32	Correct	57 ms	51576 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	5 ms	3932 KB	Output is correct
36	Correct	5 ms	10332 KB	Output is correct
37	Correct	5 ms	11608 KB	Output is correct
38	Correct	4 ms	6744 KB	Output is correct
39	Correct	5 ms	10844 KB	Output is correct
40	Correct	1 ms	348 KB	Output is correct
41	Correct	6 ms	12884 KB	Output is correct
42	Correct	45 ms	48776 KB	Output is correct
43	Correct	5 ms	10588 KB	Output is correct
44	Correct	5 ms	12380 KB	Output is correct

Subtask #6

0.0 / 42.0

#	결과	실행 시간	메모리	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	4 ms	4444 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	93 ms	57644 KB	Output is correct
9	Correct	33 ms	17612 KB	Output is correct
10	Correct	34 ms	17612 KB	Output is correct
11	Correct	85 ms	61392 KB	Output is correct
12	Correct	87 ms	61392 KB	Output is correct
13	Correct	88 ms	61392 KB	Output is correct
14	Correct	83 ms	61256 KB	Output is correct
15	Correct	86 ms	61408 KB	Output is correct
16	Correct	85 ms	61396 KB	Output is correct
17	Correct	87 ms	61392 KB	Output is correct
18	Correct	87 ms	61392 KB	Output is correct
19	Correct	89 ms	61400 KB	Output is correct
20	Correct	92 ms	61392 KB	Output is correct
21	Correct	6 ms	16704 KB	Output is correct
22	Correct	6 ms	16468 KB	Output is correct
23	Correct	10 ms	18896 KB	Output is correct
24	Correct	23 ms	31548 KB	Output is correct
25	Correct	69 ms	57812 KB	Output is correct
26	Correct	90 ms	61464 KB	Output is correct
27	Correct	90 ms	61480 KB	Output is correct
28	Correct	80 ms	61608 KB	Output is correct
29	Correct	77 ms	58620 KB	Output is correct
30	Correct	86 ms	61172 KB	Output is correct
31	Correct	97 ms	61392 KB	Output is correct
32	Correct	34 ms	20464 KB	Output is correct
33	Correct	47 ms	20464 KB	Output is correct
34	Correct	95 ms	61412 KB	Output is correct
35	Incorrect	86 ms	61396 KB	Output isn't correct
36	Halted	0 ms	0 KB	-