13475. 동선 추적

//user_code

#include <string.h>
using namespace std;
struct Place {
	int r_plus_c_idx;
	int r_minus_c_idx;
	int r_idx;
	int c_idx;
	int uID;
	int pID;
	int r;
	int c;
	int infected;
	Place* dir[8];
};

Place * place[50001];
int uIDX[10001];
Place* user[10001][100];
Place * R_plus_C[20001][10]; // 1, 5
Place * R_minus_C[20001][10]; // 3, 7
Place * R[10001][10]; 
Place * C[10001][10];

void init()
{
	memset(uIDX, 0, sizeof(uIDX));
	memset(place, NULL, sizeof(place));
	for (int i = 0; i < 20001; i++)
	{
		memset(R_minus_C[i], NULL, sizeof(R_minus_C[i]));
		memset(R_plus_C[i], NULL, sizeof(R_plus_C[i]));
	}
	for (int i = 0; i < 10001; i++)
	{
		memset(R[i], NULL, sizeof(R[i]));
		memset(C[i], NULL, sizeof(C[i]));
	}
}

void addPlace(int pID, int r, int c)
{
	place[pID] = new Place();
	place[pID]->r = r;
	place[pID]->c = c;
	place[pID]->pID = pID;
	place[pID]->infected = 0;
	int r_added = 0;
	int c_added = 0;
	int r_plus_c_added = 0;
	int r_minus_c_added = 0;

	if (pID == 25099)
		int l = 0;
	int r_minus_c = r - c + 10000;
	
	for (int i = 0; i < 10; i++)
	{
		if (r_added == 1 && c_added == 1 && r_plus_c_added == 1 && r_minus_c_added == 1)
			break;
		//add
		if (R_plus_C[r + c][i] == NULL && r_plus_c_added==0)
		{
			R_plus_C[r + c][i] = place[pID];
			place[pID]->r_plus_c_idx = i;
			r_plus_c_added = 1;
		}
		if (R_minus_C[r_minus_c][i] == NULL && r_minus_c_added == 0)
		{
			R_minus_C[r_minus_c][i] =place[pID];
			place[pID]->r_minus_c_idx = i;
			r_minus_c_added = 1;
		}
		if (R[r][i] == NULL && r_added ==0)
		{
			R[r][i] = place[pID];
			place[pID]->r_idx = i;
			r_added = 1;
		}
		if (C[c][i] == NULL && c_added == 0)
		{
			C[c][i] = place[pID];
			place[pID]->c_idx = i;
			c_added = 1;
		}
	}
}

void removePlace(int pID)
{
	int r = place[pID]->r;
	int c = place[pID]->c;
	int r_minus_c = r - c + 10000;
	R_plus_C[r+c][place[pID]->r_plus_c_idx] = NULL; // 1, 5
	R_minus_C[r_minus_c][place[pID]->r_minus_c_idx]= NULL; // 3, 7
	R[r][place[pID]->r_idx] = NULL;
	C[c][place[pID]->c_idx] = NULL;
	place[pID] = NULL;
}

void contactTracing(int uID, int visitNum, int moveInfo[], int visitList[])
{
	int visit[100];
	int min[8];
	for (int i = 0; i < 100; i++)
		visitList[i] = 0;
	int pID = moveInfo[0];
	int r = place[pID]->r;
	int c = place[pID]->c;
	place[pID]->uID = uID;
	visitList[0] = moveInfo[0];
	visit[0] = moveInfo[0];
	int info;
	
	memset(place[pID]->dir, NULL, sizeof(place[pID]->dir));

	for (int v = 1; v < visitNum; v++)
	{
		int r_minus_c = r - c + 10000;
		info = moveInfo[v];
		for (int i = 0; i < 8; i++)
		{
			min[i] = 20000;
		}
		
		for (int i = 0; i < 10; i++)
		{
			if (R[r][i] != NULL && R[r][i]->infected == 0)
			{
				if (R[r][i]->c < c && min[6] > c - R[r][i]->c)//6
				{
					place[pID]->dir[6] = R[r][i];
					place[pID]->dir[6]->dir[2] = new Place();
					place[pID]->dir[6]->dir[2] = place[pID];
					min[6] = c - R[r][i]->c;
				}
				if (R[r][i]->c > c && min[2] > R[r][i]->c - c)//2
				{
					place[pID]->dir[2] = R[r][i];
					place[pID]->dir[2]->dir[6] = new Place();
					place[pID]->dir[2]->dir[6] = place[pID];
					min[2] = R[r][i]->c - c;
				}
			}
			if (C[c][i] != NULL && C[c][i]->infected == 0)
			{
				if (C[c][i]->r > r && min[4] > C[c][i]->r - r)//4
				{
					place[pID]->dir[4] = C[c][i];
					place[pID]->dir[4]->dir[0] = new Place();
					place[pID]->dir[4]->dir[0] = place[pID];
					min[4] = C[c][i]->r - r;
				}
				if (C[c][i]->r < r && min[0] > r - C[c][i]->r)//0
				{
					place[pID]->dir[0] = C[c][i];
					place[pID]->dir[0]->dir[4] = new Place();
					place[pID]->dir[0]->dir[4] = place[pID];
					min[0] = r - C[c][i]->r;
				}
			}
			if (R_plus_C[r + c][i] != NULL && R_plus_C[r + c][i]->infected == 0)
			{
				if (R_plus_C[r + c][i]->r > r && min[5] > R_plus_C[r + c][i]->r - r)//5
				{
					place[pID]->dir[5] = R_plus_C[r + c][i];
					place[pID]->dir[5]->dir[1] = new Place();
					place[pID]->dir[5]->dir[1] = place[pID];
					min[5] = R_plus_C[r + c][i]->r - r;
				}
				if (R_plus_C[r + c][i]->r < r && min[1] > r - R_plus_C[r + c][i]->r)//1
				{
					place[pID]->dir[1] = R_plus_C[r + c][i];
					place[pID]->dir[1]->dir[5] = new Place();
					place[pID]->dir[1]->dir[5] = place[pID];
					min[1] = r - R_plus_C[r + c][i]->r;
				}
			}
			if (R_minus_C[r_minus_c][i] != NULL && R_minus_C[r_minus_c][i]->infected == 0)
			{
				if (R_minus_C[r_minus_c][i]->r > r && min[3] > R_minus_C[r_minus_c][i]->r - r)//3
				{
					place[pID]->dir[3] = R_minus_C[r_minus_c][i];
					place[pID]->dir[3]->dir[7] = new Place();
					place[pID]->dir[3]->dir[7] = place[pID];
					min[3] = R_minus_C[r_minus_c][i]->r - r;
				}
				if (R_minus_C[r_minus_c][i]->r < r && min[7] > r - R_minus_C[r_minus_c][i]->r)//7
				{
					place[pID]->dir[7] = R_minus_C[r_minus_c][i];
					place[pID]->dir[7]->dir[3] = new Place();
					place[pID]->dir[7]->dir[3] = place[pID];
					min[7] = r - R_minus_C[r_minus_c][i]->r;
				}
			}
		}
		pID = place[pID]->dir[info]->pID;
		r = place[pID]->r;
		c = place[pID]->c;
		place[pID]->uID = uID;
		visitList[v] = pID;
		visit[v] = pID;
	}
	for (int j = 0; j < visitNum; j++)
	{
		user[uID][j] = place[visitList[j]];
		place[visitList[j]]->infected = 1;
	}
	uIDX[uID] += visitNum;
}

void disinfectPlaces(int uID)
{
	for (int i = 0; i < uIDX[uID]; i++)
	{
		if (user[uID][i] == NULL)
			continue;
		user[uID][i]->infected = 0;
	}
	uIDX[uID] = 0;
	memset(user[uID], NULL, sizeof(user[uID]));
}​

13475 동선추적.pdf

0.82MB

//main
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>

extern void init();
extern void addPlace(int pID, int r, int c);
extern void removePlace(int pID);
extern void contactTracing(int uID, int visitNum, int moveInfo[], int visitList[]);
extern void disinfectPlaces(int uID);

#define	INIT				100
#define ADD_PLACE			200
#define REMOVE_PLACE		300
#define CONTACT_TRACING		400
#define DISINFECT_PLACES	500

static int run()
{
	int queryCnt;
	scanf("%d", &queryCnt);

	int ret = 0;
	int cmd;
	int pID, uID, r, c, visitNum;
	int moveInfo[100];
	int visitList[100];
	int ans;

	for (int q = 1; q <= queryCnt; q++)
	{
		scanf("%d", &cmd);

		switch (cmd) {
		case INIT:
			init();
			ret = 1;
			break;
		case ADD_PLACE:
			scanf("%d%d%d", &pID, &r, &c);
			addPlace(pID, r, c);
			break;
		case REMOVE_PLACE:
			scanf("%d", &pID);
			removePlace(pID);
			break;
		case CONTACT_TRACING:
			scanf("%d%d", &uID, &visitNum);
			for (int i = 0; i < visitNum; i++)
				scanf("%d", &moveInfo[i]);
			contactTracing(uID, visitNum, moveInfo, visitList);
			for (int i = 0; i < visitNum; i++) {
				scanf("%d", &ans);
				if (visitList[i] != ans)
					ret = 0;
			}
			break;
		case DISINFECT_PLACES:
			scanf("%d", &uID);
			disinfectPlaces(uID);
			break;
		default:
			ret = 0;
			break;
		}
	}

	return ret;
}

int main()
{
	setbuf(stdout, NULL);
	//freopen("sample_input.txt", "r", stdin);

	int tc, MARK;
	scanf("%d%d", &tc, &MARK);

	for (int t = 1; t <= tc; t++)
	{
		int score = run() ? MARK : 0;
		printf("#%d %d\n", t, score);
	}

	return 0;
}