Untitled

mail@pastecode.io avatarunknown
plain_text
2 months ago
4.5 kB
1
Indexable
Never
#define MAX 10000

struct Node{
	int row;
	int col;
	int infect;
	int next[4];
}Point[50001];

struct User{
	int N;
	int Node[101];
}user[1001];

int hTable[4][MAX*2];

void init()
{
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < MAX*2; j++)
		{
			hTable[i][j]=0;
		}
	}
	for (int i = 0; i < 1001; i++)
	{
		user[i].N=0;
	}
}

void addPlace(int pID, int r, int c)
{
	Point[pID].row=r;
	Point[pID].col=c;
	Point[pID].infect=0;

	Point[pID].next[0]=hTable[0][r];
	hTable[0][r]=pID;

	Point[pID].next[1]=hTable[1][c];
	hTable[1][c]=pID;

	Point[pID].next[2]=hTable[2][r+c];
	hTable[2][r+c]=pID;

	Point[pID].next[3]=hTable[3][r-c+MAX];
	hTable[3][r-c+MAX]=pID;

}

void deleteCustome(int pID,int id,int h){
	int tmp = hTable[id][h];
	int pre = 0;
	while(tmp){
		if(tmp == pID){
			if(pre == 0) hTable[id][h] = Point[hTable[id][h]].next[id];
			Point[pre].next[id] =Point[tmp].next[id];
		}
		pre=tmp;
		tmp=Point[tmp].next[id];
	}
}

void removePlace(int pID)
{
	deleteCustome(pID,0,Point[pID].row);
	deleteCustome(pID,1,Point[pID].col);
	deleteCustome(pID,2,Point[pID].row + Point[pID].col);
	deleteCustome(pID,3,Point[pID].row - Point[pID].col + MAX);
}

int check(int pID, int dir){
	int r = Point[pID].row;
    int c = Point[pID].col;
    int id = 0;
    int temp = MAX;
    int tmp;
    switch (dir)
    {
    case 0:
        tmp = hTable[1][c];
        while(tmp) {
            if(!Point[tmp].infect && Point[tmp].row < r && (r - Point[tmp].row) < temp) {
                id = tmp;
                temp = r - Point[tmp].row;
            }
            tmp = Point[tmp].next[1];
        }
        break;
    case 1:
        tmp = hTable[2][r+c];
        while(tmp) {
            if(!Point[tmp].infect && Point[tmp].row < r && (r - Point[tmp].row) < temp) {
                id = tmp;
                temp = r - Point[tmp].row;
            }
            tmp = Point[tmp].next[2];
        }
        break;
    case 2:
        tmp = hTable[0][r];
        while(tmp) {
            if(!Point[tmp].infect && Point[tmp].col > c && (Point[tmp].col - c) < temp) {
                id = tmp;
                temp = Point[tmp].col - c;
            }
            tmp = Point[tmp].next[0];
        }
        break;
    case 3:
        tmp = hTable[3][r - c+ MAX];
        while(tmp) {
            if(!Point[tmp].infect && Point[tmp].col > c && (Point[tmp].col - c) < temp) {
                id = tmp;
                temp = Point[tmp].col - c;
            }
            tmp = Point[tmp].next[3];
        }
        break;
    case 4:
        tmp = hTable[1][c];
        while(tmp) {
            if(!Point[tmp].infect && Point[tmp].row > r && (Point[tmp].row - r) < temp) {
                id = tmp;
                temp = Point[tmp].row - r;
            }
            tmp = Point[tmp].next[1];
        }
        break;
    case 5:
        tmp = hTable[2][r+c];
        while(tmp) {
            if(!Point[tmp].infect && Point[tmp].row > r && (Point[tmp].row - r) < temp) {
                id = tmp;
                temp = Point[tmp].row - r;
            }
            tmp = Point[tmp].next[2];
        }
        break;
    case 6:
        tmp = hTable[0][r];
        while(tmp) {
            if(!Point[tmp].infect && Point[tmp].col < c && (c - Point[tmp].col) < temp) {
                id = tmp;
                temp = c - Point[tmp].col;
            }
            tmp = Point[tmp].next[0];
        }
        break;
    case 7:
        tmp = hTable[3][r-c+MAX];
        while(tmp) {
            if(!Point[tmp].infect && Point[tmp].col < c && (c - Point[tmp].col) < temp) {
                id = tmp;
                temp = c - Point[tmp].col;
            }
            tmp = Point[tmp].next[3];
        }
        break;
    default:
        break;
    }
    return id;
}

void contactTracing(int uID, int visitNum, int moveInfo[], int visitList[])
{
	int pID = moveInfo[0];
	visitList[0] = moveInfo[0];
	user[uID].Node[user[uID].N++] = moveInfo[0];
	for(int i = 1; i < visitNum; i++) {
		int next = check(pID, moveInfo[i]);
		visitList[i] = pID = next;
		user[uID].Node[user[uID].N++] = next;
	}

	for(int i = 0; i < visitNum; i++) 
		Point[visitList[i]].infect = 1;
}

void disinfectPlaces(int uID)
{
	 for(int i =0; i < user[uID].N; i++) {
        Point[user[uID].Node[i]].infect = 0;
    }
}