Untitled

mail@pastecode.io avatar
unknown
plain_text
14 days ago
5.8 kB
5
Indexable
Never
#include<iostream>
#include<queue>
  
using namespace std;
  
struct Bacteria
{
    int id;
    int size;
    int time;
}Bacteria_pool[3003];
  
int Map[202][202];
int N;
  
  
struct Result
{
    int row;
    int col;
};
  
  
  
struct Q {
    int x;
    int y;
    int d;
}q[20002];
  
int ts = 0;
int visited[202][202];
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
  
struct node
{
    int x, y, dis;
};
  
  
  
struct cmp {
    bool operator()(const node &a, const node &b)const {
        if (a.dis == b.dis)
        {
            if (a.x == b.x)
            {
                return a.y > b.y;
            }
            return a.x > b.x;
        }
        return a.dis > b.dis;
    }
};
  
  
  
  
  
void init(int N)
{
  
  
    ::N = N;
    for (int i = 0; i <= N; i++)
    {
        for (int j = 0; j <= N; j++)
        {
            Map[i][j] = 0;
        }
    }
  
  
}
  
  
  
  
int check(int x, int y, int stime, Bacteria b)
{
    int w = 0, r = 0;
    if (Bacteria_pool[Map[x][y]].time > stime)
        return 0;
    q[w++] = { x,y };
    visited[x][y] = ++ts;
  
    while (w != r)
    {
        Q temp = q[r++];
  
        for (int i = 0; i < 4; i++)
        {
            int nx = temp.x + dx[i];
            int ny = temp.y + dy[i];
            if (nx <1 || nx >N || ny <1 || ny >N || visited[nx][ny] == ts)
                continue;
            if (Bacteria_pool[Map[nx][ny]].time <= stime)
            {
                visited[nx][ny] = ts;
                q[w++] = { nx, ny };
                if (w >= b.size) return 1;
            }
        }
    }
    return 0;
}
  
Result putBacteria(int mTime, int mRow, int mCol, Bacteria mBac)
{
    if (!check(mRow, mCol, mTime, mBac))
        return { 0,0 };
    int count = mBac.size;
    priority_queue<node, vector<node>, cmp>  pq;
    pq.push({ mRow, mCol,0 });
  
    visited[mRow][mCol] = ++ts;
    Bacteria_pool[mBac.id] = { mBac.id, mBac.size, mTime + mBac.time };
  
    while (!pq.empty()) {
        node t = pq.top();
        pq.pop();
  
        Map[t.x][t.y] = mBac.id;
        if (--count == 0) return { t.x, t.y };
        for (int i = 0; i < 4; i++) {
            int nx = t.x + dx[i], ny = t.y + dy[i];
            if (nx < 1 || ny < 1 || nx> N || ny > N || visited[nx][ny] == ts) continue;
            if (Bacteria_pool[Map[nx][ny]].time <= mTime) {
                visited[nx][ny] = ts;
                node temp;
                temp.x = nx;
                temp.y = ny;
                temp.dis = abs(mRow - nx) + abs(mCol - ny);
                pq.push(temp);
            }
        }
    }
    return { 0, 0 };
  
  
  
}
  
int checkCell(int mTime, int mRow, int mCol) { return Bacteria_pool[Map[mRow][mCol]].time <= mTime ? 0 : Bacteria_pool[Map[mRow][mCol]].id; }
  
int killBacteria(int mTime, int mRow, int mCol)
{
    int res = checkCell(mTime, mRow, mCol);
    if (res)
        Bacteria_pool[Map[mRow][mCol]].time = -1;
    return res;
}

/*
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>

struct Result
{
	int row;
	int col;
};

struct Bacteria
{
	int id;
	int size;
	int time;
};

extern void init(int N);
extern Result putBacteria(int mTime, int mRow, int mCol, Bacteria mBac);
extern int killBacteria(int mTime, int mRow, int mCol);
extern int checkCell(int mTime, int mRow, int mCol);

/////////////////////////////////////////////////////////////////////////

#define INIT	10000
#define PUT		20000
#define KILL	30000
#define CHECK	40000

static bool run()
{
	int cmd, N, time, row, col, ans, ret;
	Result ret_bac;
	Bacteria bac;

	int Q = 0;
	bool okay = false;

	scanf("%d", &Q);
	for (int q = 0; q < Q; ++q)
	{
		scanf("%d", &cmd);
		switch (cmd)
		{
		case INIT:
			scanf("%d", &N);
			init(N);
			okay = true;
			break;

		case PUT:
			scanf("%d %d %d %d %d %d", &time, &row, &col, &bac.id, &bac.size, &bac.time);
			ret_bac = putBacteria(time, row, col, bac);
			scanf("%d %d", &row, &col);
			if (ret_bac.row != row || ret_bac.col != col) {
				okay = false;
			}
			break;

		case KILL:
			scanf("%d %d %d %d", &time, &row, &col, &ans);
			ret = killBacteria(time, row, col);
			if (ret != ans) {
				okay = false;
			}
			break;

		case CHECK:
			scanf("%d %d %d %d", &time, &row, &col, &ans);
			ret = checkCell(time, row, col);
			if (ret != ans) {
				okay = false;
			}
			break;

		default:
			okay = false;
		}
	}

	return okay;
}

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

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

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

	return 0;
}

*/
25 100
40
10000 10
20000 1 3 8 1 11 33 4 7
20000 2 2 4 2 8 159 2 2
40000 4 2 9 1
20000 5 1 6 3 9 90 0 0
40000 6 2 1 0
20000 9 2 10 4 5 87 0 0
20000 10 4 2 5 16 112 6 3
20000 13 1 2 6 4 116 0 0
20000 15 6 5 7 12 100 5 7
20000 19 8 3 8 47 117 0 0
40000 20 5 4 5
20000 21 10 5 9 5 97 9 4
40000 25 6 7 7
20000 26 3 5 10 15 89 0 0
20000 27 1 9 11 13 34 0 0
20000 29 8 7 12 27 125 0 0
40000 31 7 4 7
20000 34 1 9 13 13 105 4 9
20000 35 7 9 14 7 81 6 8
40000 39 3 6 0
20000 41 5 10 15 4 97 0 0
20000 48 9 7 16 15 95 0 0
40000 49 5 4 5
20000 60 3 6 17 9 79 0 0
20000 61 8 2 18 15 57 0 0
30000 62 8 2 0
40000 73 7 8 14
20000 74 8 10 19 5 76 9 8
30000 85 9 5 9
20000 87 8 4 20 15 27 10 3
40000 88 6 3 5
30000 89 3 7 0
20000 92 10 3 21 7 81 0 0
20000 93 10 1 22 4 130 0 0 
20000 95 9 7 23 11 51 0 0
20000 96 9 7 24 5 115 10 5
20000 99 8 8 25 2 131 0 0
20000 100 10 9 26 2 58 0 0
40000 110 9 8 19
Leave a Comment