Untitled
unknown
plain_text
a year ago
10 kB
31
Indexable
//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