Untitled

 avatar
unknown
plain_text
2 years ago
3.6 kB
9
Indexable
#include <iostream>
using namespace std;
#include <map>
#include <string>
struct node{
	long long hashVal;
	int val[5];
};

const int maxxVal = 531445;
node rooms[30010];
map<string, int> mmap;
int res[3][maxxVal][2], currentID, nRoom;
int mDirs[5] = {0,0,1,2,2};
int base[4] = {1, 27, 729, 19683};

void init()
{
	nRoom = 0;
	currentID = -1;
	mmap.clear();
	for(int i = 0; i<3; i++)
		for(int j=0; j<maxxVal; j++)
		{
			res[i][j][0] = -1;
			res[i][j][1] = -1;
		}
}

bool removeRes(int mID, int val, int mDir){
	if(res[mDir][val][0] == mID){
		res[mDir][val][0] = res[mDir][val][1];
		res[mDir][val][1] = -1;
		return true;
	}
	else if(res[mDir][val][1] == mID){
		res[mDir][val][1] = -1;
		return true;
	}

	return false;
}
void analyzeWord(int mID, char mWord[], int mDirLen[]){
	rooms[mID].hashVal = 0;
	for(int i=0; i<11; i++)
	{
		mWord[i] -= ('a' - 1);
		rooms[mID].hashVal = rooms[mID].hashVal * base[1] + mWord[i];
	}

	rooms[mID].val[0] = mWord[0] * base[1] + mWord[1];
	rooms[mID].val[1] = rooms[mID].val[0] * base[2] + mWord[2] * base[1] + mWord[3];
	rooms[mID].val[2] = mWord[4] * base[2] + mWord[5] * base[1] + mWord[6];
	rooms[mID].val[3] = mWord[9] * base[1] + mWord[10];
	rooms[mID].val[4] = mWord[7] * base[3] + mWord[8] * base[2] + rooms[mID].val[3];
	if(mDirLen[0] == 4) swap(rooms[mID].val[0], rooms[mID].val[1]);
	if(mDirLen[2] == 4) swap(rooms[mID].val[3], rooms[mID].val[4]);
}
void updateRes(int mID, int val, int mDir)
{
	int minID1 = res[mDir][val][0];
	int minID2 = res[mDir][val][1];

	if(mID == minID1 || mID == minID2)
		return;
	if(minID1 == -1){
		res[mDir][val][0] = mID;
	}
	else{
		if(rooms[minID1].hashVal > rooms[mID].hashVal){
			res[mDir][val][1] = res[mDir][val][0];
			res[mDir][val][0] = mID;
		}
		else if(minID2 == -1 || rooms[minID2].hashVal > rooms[mID].hashVal)
			res[mDir][val][1] = mID;
	}
}

void addRoom(int mID, char mWord[], int mDirLen[])
{
	if(nRoom < mID)
		nRoom = mID;
	mmap[mWord] = mID;
	analyzeWord(mID, mWord, mDirLen);
	for(int i=0; i<5; i++)
		updateRes(mID, rooms[mID].val[i], mDirs[i]);
}
void setCurrent(char mWord[])
{
	currentID = mmap[mWord];
}

int moveDir(int mDir)
{
	int nextMDir = abs(mDir - 2);
	int val = rooms[currentID].val[2];
	switch(mDir){
		case 0: val = rooms[currentID].val[0]; break;
		case 2: val = rooms[currentID].val[3]; break;
	}

	int pos1 = res[nextMDir][val][0];
	int pos2 = res[nextMDir][val][1];
	if(pos1 == -1 || (pos1 == currentID && pos2 == -1))
		return 0;

	currentID = pos1 != currentID ? pos1 : pos2;
	return currentID;
}

void changeWord(char mWord[], char mChgWord[], int mChgLen[])
{
	//Remove old
	int mID = mmap[mWord];
	bool hasChanged = false;
	for(int i=0; i<5; i++)
		hasChanged |= removeRes(mID, rooms[mID].val[i], mDirs[i]);
	if(hasChanged)
	{
		for(int i=1; i<=nRoom; i++)
		{
			if(i != mID){
				if(rooms[i].val[0] == rooms[mID].val[0] || rooms[i].val[0] == rooms[mID].val[1])
					updateRes(i, rooms[i].val[0], 0);
				if(rooms[i].val[1] == rooms[mID].val[0] || rooms[i].val[1] == rooms[mID].val[1])
					updateRes(i, rooms[i].val[1], 0);
				if(rooms[i].val[2] == rooms[mID].val[2])
					updateRes(i, rooms[i].val[2], 1);
				if(rooms[i].val[3] == rooms[mID].val[3] || rooms[i].val[3] == rooms[mID].val[4])
					updateRes(i, rooms[i].val[3], 2);
				if(rooms[i].val[4] == rooms[mID].val[3] || rooms[i].val[4] == rooms[mID].val[4])
					updateRes(i, rooms[i].val[4], 2);
			}
		}
	}
	//add new
	addRoom(mID, mChgWord, mChgLen);
}	
Editor is loading...