Untitled
unknown
plain_text
a year ago
12 kB
6
Indexable
#include <vector>
#include <queue>
#define MAXHASING 10007
#define MAXN 8000
using namespace std;
vector<int> group[MAXHASING+1];
vector<int> _pre[MAXN];
vector<int> _next[MAXN];
int sizeNext[MAXN];
queue<int> callback;
int pre_[MAXN];
int next_[MAXN];
bool matchTone(int MotiveFirst[], int MotiveSecond[]){
int cnt = 0;
for(int i = 0; i < 4; ++i){
if(MotiveFirst[i] != MotiveSecond[i]){
++cnt;
}
}
return cnt <= 2;
}
int hashing(int arr[]){
return (arr[0] + arr[1]*6 + arr[2] * 36 + arr[3] * 216);
}
void compose(int N, int mTone[MAXN][2][4], int mBeat[MAXN][2][4], int mAns[MAXN])
{
int h;
for(int i = 0; i < MAXHASING; ++i){
group[i].clear();
}
for(int i = 0; i < N; ++i){
h = hashing(mBeat[i][0]);
group[h].push_back(i);
_pre[i].clear();
_next[i].clear();
}
for(int i = 0; i < N; ++i){
h = hashing(mBeat[i][1]);
for(auto j: group[h]){
if(i != j && matchTone(mTone[i][1], mTone[j][0])){
_pre[j].push_back(i);
_next[i].push_back(j);
}
}
sizeNext[i] = _next[i].size();
if(sizeNext[i] == 1){
callback.push(i);
}
}
for(int i = 0; i < N; ++i){
pre_[i] = next_[i] = -1;
}
while (!callback.empty())
{
int id = callback.front();
callback.pop();
for(auto i: _next[id]){
if(pre_[i] == -1){
pre_[i] = id;
next_[id] = i;
for(auto ii: _pre[i]){
--sizeNext[ii];
if(sizeNext[ii] == 1){
callback.push(ii);
}
}
break;
}
}
}
for(int i = 0, p = 0; i < N; ++i, p = next_[p]){
mAns[i] = p;
}
}
//int main(){
// int T[MAXN][2][4] = {{{0, 0, 0, 4}, {0, 2, 8, 0}}, {{15, 12, 3, 5}, {0, 1, 12, 11}},
// {{0, 2, 4, 1}, {0, 1, 4, 1}}, {{0, 11, 1, 15}, {0, 0, 14, 2}},
// {{0, 2, 14, 2}, {0, 3, 2, 1}}, {{0, 1, 4, 11}, {0, 3, 3, 5}},
// {{8, 8, 8, 0}, {0, 0, 15, 15}}, {{0, 2, 14, 4}, {0, 2, 9, 10}}};
// int B[MAXN][2][4] = {{{4, 1, 2, 1}, {2, 2, 2, 2}}, {{1, 5, 1, 1}, {4, 2, 1, 1}}, {{2, 2, 2, 2},
// {1, 5, 1, 1}}, {{3, 2, 1, 2}, {1, 2, 3, 2}}, {{1, 3, 2, 2}, {2, 2, 2, 2}},
// {{1, 5, 1, 1}, {1, 5, 1, 1}}, {{2, 2, 2, 2}, {3, 2, 1, 2}}, {{1, 2, 3, 2}, {1, 3, 2, 2}}};
// int ans[MAXN] = {};
// compose(8, T, B, ans);
// // ans = {0, 6, 3, 7, 4, 2, 5, 1};
// return 0;
//}
///
#include <vector>
#include <queue>
using namespace std;
#define MAXN 8000
int N;
int uTone[MAXN][2][4];
int uBeat[MAXN][2][4];
vector<int> Group[125];
vector<int> NextCan[MAXN];
vector<int> PreCan[MAXN];
int CntCan[MAXN];
int Next[MAXN];
int Pre[MAXN];
queue<int> que;
bool match(int a, int b)
{
int MissCnt = 0;
for (int i = 0; i < 4; ++i)
if (uTone[a][1][i] != uTone[b][0][i])
++MissCnt;
return MissCnt <= 2;
}
int geth(int arr[])
{
return (arr[0] - 1) * 25 + (arr[1] - 1) * 5 + arr[2] - 1;
}
void compose(int N, int mTone[MAXN][2][4], int mBeat[MAXN][2][4], int mAns[MAXN])
{
::N = N;
for (int i = 0; i < 125; ++i)
Group[i].clear();
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < 2; ++j)
for (int k = 0; k < 4; ++k)
{
uTone[i][j][k] = mTone[i][j][k];
uBeat[i][j][k] = mBeat[i][j][k];
}
int h = geth(uBeat[i][0]);
Group[h].push_back(i);
NextCan[i].clear();
PreCan[i].clear();
}
while (!que.empty()) que.pop();
for (int i = 0; i < N; ++i)
{
int h = geth(uBeat[i][1]);
for (auto j : Group[h])
if (i != j && match(i, j))
{
NextCan[i].push_back(j);
PreCan[j].push_back(i);
}
CntCan[i] = NextCan[i].size();
if (CntCan[i] == 1)
que.push(i);
}
for (int i = 0; i < N; ++i)
Pre[i] = Next[i] = -1;
while (!que.empty())
{
int idx1 = que.front(); que.pop();
for (auto idx2 : NextCan[idx1])
if (Pre[idx2] == -1)
{
Pre[idx2] = idx1;
Next[idx1] = idx2;
for (auto idx3 : PreCan[idx2])
{
--CntCan[idx3];
if (CntCan[idx3] == 1)
que.push(idx3);
}
break;
}
}
mAns[0] = 0;
for (int i = 0, p = 0; i < N; ++i, p = Next[p])
mAns[i] = p;
}
///
//bài pro H2320 sử dụng 2 loại hash
//[Lê Văn Bình] 09-14-2023 12:22
//#include<vector>
//#include<string>
//#include<algorithm>
//
//#define HASH_SIZE 12007
//
////string 3->11;
//
//using namespace std;
//
//struct Bacteria{
// string id;
// int fDay;
// int lDay;
// int level;
// Bacteria *parent;
//};
//
//Bacteria pool [HASH_SIZE];
//int poolIdx;
//Bacteria* hashMap[HASH_SIZE];
//
//int str2Int(char c){
// if(c>='a'&&c<='z')
// return c-'a'+1;
// return c-'A'+1;
//}
//
//void addToHashMap(Bacteria *b){
// string name= b->id;
// int hIdx = 0;
// if(name.size()>6){
// for(int i=0;i<6;i++){
// hIdx=hIdx*27+str2Int(name[i]);
// }
// }
// else {
// for(int i=0;i<name.size();i++){
// hIdx=hIdx*27+str2Int(name[i]);
// }
// }
// hIdx=hIdx%HASH_SIZE;
// while (hashMap[hIdx]!=nullptr){
// hIdx=(hIdx+1)%HASH_SIZE;
// }
// hashMap[hIdx]=b;
//}
//
//Bacteria* getBactaria(string name){
// int hIdx=0;
// if(name.size()>6){
// for(int i=0;i<6;i++){
// hIdx=hIdx*27+str2Int(name[i]);
// }
// }
// else {
// for(int i=0;i<name.size();i++){
// hIdx=hIdx*27+str2Int(name[i]);
// }
// }
// hIdx=hIdx%HASH_SIZE;
// while (hashMap[hIdx]->id!=name){
// hIdx=(hIdx+1)%HASH_SIZE;
// }
// return hashMap[hIdx];
//}
//
//void resetHash(){
// for(int i=0;i<HASH_SIZE;i++){
// hashMap[i]=nullptr;
// }
//}
//
//Bacteria* makeBactaria(string name,int firstDay, int lastDay,int lvl, Bacteria* par){
// pool[poolIdx].id=name;
// pool[poolIdx].fDay=firstDay;
// pool[poolIdx].lDay=lastDay;
// pool[poolIdx].level=lvl;
// pool[poolIdx].parent=par;
// return &pool[poolIdx++];
//}
//
//
//vector<int>birthTime,deathTime;
//
//void init(char mAncestor[], int mDeathday)
//{
// poolIdx=0;
// birthTime.clear();
// deathTime.clear();
// resetHash();
// addToHashMap(makeBactaria(mAncestor,0,mDeathday,0,nullptr));
// birthTime.push_back(0);
// deathTime.push_back(mDeathday);
// return;
//}
//
//
//int add(char mName[], char mParent[], int mBirthday, int mDeathday)
//{
// Bacteria *p = getBactaria(mParent);
// addToHashMap(makeBactaria(mName,mBirthday,mDeathday,p->level+1,p));
//
// birthTime.insert(lower_bound(birthTime.begin(),birthTime.end(),mBirthday),mBirthday);
// deathTime.insert(lower_bound(deathTime.begin(),deathTime.end(),mDeathday),mDeathday);
// return p->level+1;
//}
//
//int distance(char mName1[], char mName2[])
//{
// string n1=mName1;
// string n2=mName2;
// if(n1==n2) return 0;
// Bacteria *p1 = getBactaria(mName1);
// Bacteria *p2 = getBactaria(mName2);
// if(p1->level>p2->level)
// swap(p1,p2);
// int ret=0;
// while (p1->level!=p2->level){
// p2=p2->parent;
// ret++;
// }
// while(p1!=p2){
// p1=p1->parent;
// p2=p2->parent;
// ret+=2;
// }
// return ret;
//}
//
//int count(int mDay)
//{
// int n_b = upper_bound(birthTime.begin(),birthTime.end(),mDay)-birthTime.begin();
// int n_d = upper_bound(deathTime.begin(),deathTime.end(),mDay-1)-deathTime.begin();
// return n_b-n_d;
//}
//
//[Lê Văn Bình] 09-14-2023 12:22
//#include<vector>
//#include<algorithm>
//
//
////H2320 [pro] bacteriaFamily HASH-LINKLIST
//
//#define HASH_SIZE 1999
//#define MAXN 12007
//#define rint register int
//#define F(i,a,b) for(rint i=a;i<b;++i)
//#define FD(i,a,b,c) for(rint i=a;c[i]!=b;++i)
//
////string 3->11;
//
//using namespace std;
//typedef long long ll;
//
//struct Bacteria{
// ll id;
// int fDay;
// int lDay;
// int level;
// Bacteria *next;
// Bacteria *parent;
//}pool [MAXN];
//int poolIdx;
//Bacteria* hashMap[HASH_SIZE];
//vector<int>birthTime,deathTime;
//
////covert char to int
//int str2Int(char c){
// if(c>='a'&&c<='z')
// return c-'a'+1;
// return c-'A'+1;
//}
////conver char to longlong
//ll str2ll(char c[]){
// ll id=0;
// FD(i,0,'\0',c){
// id=id*27+str2Int(c[i]);
// }
// return id;
//}
//
//void addToHashMap(Bacteria *b){
// ll hIdx = 0;
// hIdx=b->id%HASH_SIZE;
// if(!hashMap[hIdx]) {
// hashMap[hIdx]=b;
// return;
// }
// Bacteria *cur = hashMap[hIdx] ;
// while (cur->next!=nullptr){
// cur=cur->next;
// }
// cur->next=b;
//}
//
//Bacteria* getBactaria(ll id){
// int hIdx=id%HASH_SIZE;
// Bacteria *ret = hashMap[hIdx];
// while (ret->id!=id){
// ret=ret->next;
// }
// return ret;
//}
//
//void resetHash(){
// F(i,0,HASH_SIZE){
// hashMap[i]=nullptr;
// }
//}
//
//
//Bacteria* makeBactaria(char name[],int firstDay, int lastDay,int lvl, Bacteria* par){
// pool[poolIdx].id=str2ll(name);
// pool[poolIdx].fDay=firstDay;
// pool[poolIdx].lDay=lastDay;
// pool[poolIdx].level=lvl;
// pool[poolIdx].parent=par;
// pool[poolIdx].next=nullptr;
// return &pool[poolIdx++];
//}
//
//
//
//
//void init(char mAncestor[], int mDeathday)
//{
// poolIdx=0;
// birthTime.clear();
// deathTime.clear();
// resetHash();
// addToHashMap(makeBactaria(mAncestor,0,mDeathday,0,nullptr));
// birthTime.push_back(0);
// deathTime.push_back(mDeathday);
// return;
//}
//
//
//int add(char mName[], char mParent[], int mBirthday, int mDeathday)
//{
// Bacteria *p = getBactaria(str2ll(mParent));
// addToHashMap(makeBactaria(mName,mBirthday,mDeathday,p->level+1,p));
//
// birthTime.insert(lower_bound(birthTime.begin(),birthTime.end(),mBirthday),mBirthday);
// deathTime.insert(lower_bound(deathTime.begin(),deathTime.end(),mDeathday),mDeathday);
// return p->level+1;
//}
//
//int distance(char mName1[], char mName2[])
//{
// ll n1=str2ll(mName1);
// ll n2=str2ll(mName2);
// if(n1==n2) return 0;
// Bacteria *p1 = getBactaria(n1);
// Bacteria *p2 = getBactaria(n2);
// if(p1->level>p2->level)
// swap(p1,p2);
// int ret=0;
// while (p1->level!=p2->level){
// p2=p2->parent;
// ret++;
// }
// while(p1!=p2){
// p1=p1->parent;
// p2=p2->parent;
// ret+=2;
// }
// return ret;
//}
//
//int count(int mDay)
//{
// int n_b = upper_bound(birthTime.begin(),birthTime.end(),mDay)-birthTime.begin();
// int n_d = upper_bound(deathTime.begin(),deathTime.end(),mDay-1)-deathTime.begin();
// return n_b-n_d;
//}
//
//[Lê Văn Bình] 09-14-2023 12:22
//trên dùng mảng dưới dùng linked-list