Untitled
plain_text
24 days ago
10 kB
11
Indexable
Never
//user #include <vector> #include <queue> using namespace std; #define PII pair<int, int> #define ABS(a, b) ((a) > (b) ? ((a) - (b)) : ((b) - (a))) priority_queue<int> Cells; priority_queue<PII> eraseBac; struct Result { int row; int col; }; struct Bacteria { int id; int size; int time; }; int Map[201][201]; int visitMap[201][201]; int vKey; struct { int active; int groupid; int cnt; vector<PII> nearCells; } Bac[3001]; int visitBac[3001]; int bacKey; int N; void init(int _N) { N = _N; for (int i = 1; i <= N; i++) { for (int k = 1; k <= N; k++) { Map[i][k] = 0; visitMap[i][k] = 0; } } vKey = 0; for (int i = 0; i <= 3000; i++) visitBac[i] = 0; bacKey = 0; eraseBac = {}; Bac[0].active = 0; Bac[0].groupid = 0; Bac[0].cnt = N * N; Bac[0].nearCells.clear(); } int get_bid(int bid) { if (bid == Bac[bid].groupid) return bid; Bac[bid].groupid = get_bid(Bac[bid].groupid); return Bac[bid].groupid; } void deactive_bac(int bid) { if (Bac[bid].active != 1) return; Bac[bid].active = 0; bacKey++; visitBac[bid] = bacKey; for (PII cell : Bac[bid].nearCells) { int nid = get_bid(Map[cell.first][cell.second]); if (visitBac[nid] == bacKey) continue; visitBac[nid] = bacKey; if (Bac[nid].active == 0) { Bac[nid].groupid = bid; Bac[bid].cnt += Bac[nid].cnt; } } } void process(int curTime) { while (!eraseBac.empty()) { auto e = eraseBac.top(); int etime = -e.first; int bid = e.second; if (etime > curTime) break; eraseBac.pop(); deactive_bac(bid); } } int dx[4] = { 0, 0, -1, 1 }; int dy[4] = { -1, 1, 0, 0 }; Result put_bac(int bid, int size, int row, int col) { vKey++; Cells = {}; Cells.push(-(row << 8 | col)); visitMap[row][col] = vKey; int cRow = row; int cCol = col; while (size > 0 && !Cells.empty()) { int num = -Cells.top(); row = (num >> 8) & 0xff; col = num & 0xff; Cells.pop(); if (Bac[Map[row][col]].active == 1) continue; Map[row][col] = bid; Bac[bid].cnt++; size--; int x, y, nid; for (int i = 0; i < 4; i++) { y = row + dy[i]; x = col + dx[i]; if (x < 1 || N < x || y < 1 || N < y) continue; if (visitMap[y][x] != vKey) { visitMap[y][x] = vKey; nid = get_bid(Map[y][x]); if (Bac[nid].active == 0) { int dis = ABS(cRow, y) + ABS(cCol, x); Cells.push(-(dis << 16 | y << 8 | x)); } Bac[bid].nearCells.push_back({ y, x }); } } } if (size > 0) return { 0, 0 }; return { row, col }; } Result putBacteria(int mTime, int mRow, int mCol, Bacteria mBac) { process(mTime); Bac[mBac.id].active = 0; Bac[mBac.id].groupid = mBac.id; Bac[mBac.id].cnt = 0; Bac[mBac.id].nearCells.clear(); int bid = get_bid(Map[mRow][mCol]); if (Bac[bid].active == 1) { return { 0, 0 }; } if (mBac.size > Bac[bid].cnt) { return { 0, 0 }; } Bac[mBac.id].active = 1; Result ret = put_bac(mBac.id, mBac.size, mRow, mCol); Bac[bid].cnt -= Bac[mBac.id].cnt; if (ret.row == 0) { Bac[mBac.id].active = 0; return { 0, 0 }; } eraseBac.push({ -(mTime + mBac.time), mBac.id }); return ret; } int killBacteria(int mTime, int mRow, int mCol) { process(mTime); int bid = get_bid(Map[mRow][mCol]); if (Bac[bid].active == 0) return 0; deactive_bac(bid); return bid; } int checkCell(int mTime, int mRow, int mCol) { process(mTime); int bid = get_bid(Map[mRow][mCol]); if (Bac[bid].active == 0) return 0; return bid; } //main #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; } //input 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 100 10000 10 20000 10 6 7 1 18 2122 5 9 20000 13 8 5 2 11 844 6 4 20000 22 7 2 3 18 2261 4 1 20000 26 1 9 4 5 1556 1 7 20000 31 10 1 5 10 128 0 0 20000 38 3 4 6 82 19936 0 0 20000 40 2 1 7 83 19703 0 0 20000 43 3 9 8 71 19963 0 0 20000 44 2 1 9 51 19738 0 0 20000 49 10 3 10 17 2975 0 0 20000 50 7 10 11 76 19991 0 0 20000 53 2 1 12 40 19891 8 10 20000 62 10 1 13 20 19932 0 0 20000 71 9 10 14 10 972 0 0 20000 79 10 1 15 5 1580 0 0 20000 84 10 1 16 19 1578 0 0 20000 88 10 8 17 12 541 0 0 20000 97 10 9 18 15 2604 0 0 20000 104 10 10 19 9 1081 0 0 20000 105 9 10 20 5 2807 10 8 20000 111 10 3 21 6 1949 0 0 20000 112 10 3 22 20 19836 0 0 20000 121 10 1 23 14 2729 0 0 20000 130 10 4 24 13 2183 0 0 20000 132 2 3 25 14 2495 0 0 30000 135 10 3 0 20000 136 10 4 26 15 588 0 0 20000 137 10 4 27 9 263 0 0 20000 144 10 1 28 13 2780 0 0 20000 147 10 3 29 13 539 0 0 20000 152 10 4 30 10 2252 0 0 20000 160 10 3 31 10 984 0 0 20000 169 3 9 32 10 2931 0 0 20000 175 10 3 33 8 2625 0 0 20000 181 10 1 34 10 2976 0 0 20000 186 10 1 35 16 549 0 0 20000 196 10 1 36 18 2754 0 0 20000 197 10 1 37 14 2587 0 0 20000 206 10 4 38 7 117 0 0 20000 215 10 3 39 12 875 0 0 20000 219 10 3 40 18 1187 0 0 20000 224 10 1 41 5 827 0 0 20000 232 10 1 42 18 2099 0 0 30000 238 10 3 0 20000 243 10 3 43 6 1363 0 0 20000 250 10 4 44 8 1412 0 0 20000 251 10 1 45 20 19828 0 0 20000 261 10 1 46 15 2160 0 0 20000 263 10 1 47 11 2701 0 0 20000 270 10 4 48 3 218 0 0 20000 272 10 4 49 3 1052 0 0 20000 279 10 1 50 3 395 0 0 20000 280 6 2 51 20 19795 0 0 20000 289 10 3 52 15 1707 0 0 20000 294 10 4 53 20 19870 0 0 20000 304 10 4 54 5 1108 0 0 20000 313 10 1 55 3 200 0 0 20000 322 10 3 56 9 2818 0 0 20000 327 10 3 57 13 1790 0 0 20000 332 10 4 58 9 2378 0 0 20000 334 10 3 59 8 1301 0 0 20000 342 10 1 60 5 2584 0 0 20000 347 10 3 61 7 2235 0 0 20000 353 10 4 62 10 2994 0 0 20000 358 10 3 63 16 1997 0 0 20000 366 10 1 64 11 1506 0 0 20000 373 10 4 65 17 644 0 0 20000 380 10 4 66 13 2332 0 0 20000 386 4 6 67 13 2971 0 0 20000 390 10 4 68 6 1019 0 0 20000 400 10 4 69 14 2449 0 0 20000 406 10 1 70 10 1601 0 0 20000 410 10 4 71 11 2566 0 0 20000 420 10 1 72 14 1844 0 0 20000 427 10 3 73 5 2697 0 0 20000 437 10 4 74 20 19849 0 0 20000 440 10 3 75 17 1368 0 0 20000 445 10 3 76 10 2271 0 0 20000 446 10 1 77 13 1456 0 0 20000 451 10 1 78 17 937 0 0 20000 454 10 3 79 11 2296 0 0 20000 458 10 3 80 15 337 0 0 20000 465 10 3 81 3 544 0 0 20000 468 10 3 82 17 2396 0 0 20000 477 10 1 83 11 2017 0 0 20000 486 10 1 84 19 601 0 0 20000 492 10 3 85 17 2594 0 0 20000 494 10 3 86 15 268 0 0 20000 502 10 4 87 6 1016 0 0 20000 512 10 1 88 16 753 0 0 30000 513 10 3 0 20000 521 10 3 89 9 2970 0 0 20000 531 10 3 90 13 2356 0 0 20000 533 10 4 91 11 1893 0 0 20000 535 10 3 92 3 1529 0 0 20000 545 10 3 93 10 412 0 0 20000 554 6 9 94 10 2782 0 0 20000 559 10 4 95 19 2798 0 0 20000 563 10 1 96 12 455 0 0