Untitled
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...