Untitled
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