Submission #1228419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228419		amine_aroua	Hieroglyphs (IOI24_hieroglyphs)	C++20	0 / 100	31 ms	7444 KiB

hieroglyphs

#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
int len = 0;
int N = 0 , M = 0 , oneA , oneB , zerA , zerB;
vector<vector<int>> posA , posB;
vector<int> find_ucs(int x , vector<int> A , vector<int> B)
{
	vector<int> cur;
	int mn = min((int)posA[x].size() , (int)posB[x].size());
	if(mn == 0)
	{
		int nb = min((int)posA[x^1].size() , (int)posB[x^1].size());
		while(nb--)
			cur.push_back(x^1);
		return cur;
	}
	int prv = min(posA[x][0] , posB[x][0]);
	while(prv--)
		cur.push_back(x^1);
	cur.push_back(x);
	int i = 0;
	int a = posA[x][i] , b = posB[x][i];
	int cntA = posA[x^1].end() - upper_bound(posA[x^1].begin() , posA[x^1].end() , a);
	int cntB = posB[x^1].end() - upper_bound(posB[x^1].begin() , posB[x^1].end() , b);
	prv = min(cntA , cntB);
	for( ; i < mn ; i++)
	{
		a = posA[x][i] , b = posB[x][i];
		cntA = posA[x^1].end() - upper_bound(posA[x^1].begin() , posA[x^1].end() , a);
		cntB = posB[x^1].end() - upper_bound(posB[x^1].begin() , posB[x^1].end() , b);
		int now = min(cntA , cntB);
		while(now != prv)
		{
			cur.push_back(x^1);
			prv--;
		}
		cur.push_back(x);
	}
	return cur;
}
std::vector<int> ucs(std::vector<int> A, std::vector<int> B) 
{
	N = (int)A.size();
	M = (int)B.size();
	posA.assign(2 ,vector<int>(N));
	posB.assign(2 ,vector<int>(M));
	zerA = 0 ,zerB = 0;
	for(int i = 0 ; i < N ; i++)
	{
		posA[A[i]].push_back(i);
		if(A[i] == 0)
			zerA++;
	}
	for(int i = 0 ; i < M ; i++)
	{
		posB[B[i]].push_back(i);
		if(B[i] == 0)
			zerB++;
	}
	oneA = N - zerA;
	oneB = M - zerB;
	len = min(zerA , zerB) + min(oneA , oneB);
	vector<int> a = find_ucs(0 , A , B);
	vector<int> b = find_ucs(1 , A , B);
	if(a != b || (int)a.size() != len)
	{
		return {-1};
	}
	return a;
}

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