Untitled
unknown
plain_text
a year ago
15 kB
20
Indexable
---------------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;
}
--------------USER----------------
#define MAX_N 201
#define MAX_BACTERIAL 3001
#define MAX_HEAP 201*201
#include <iostream>
using namespace std;
struct Result
{
int row;
int col;
};
struct Bacteria
{
int id;
int size;
int time;
Bacteria(){
id = 0;
size = 0;
time = 0;
}
};
struct Node{
int row, col;
int dis;
void setNode(int r, int c, int d){
this->row = r;
this->col = c;
this->dis = d;
}
bool operator>(const Node& n){
if(dis != n.dis) return dis < n.dis;
if(row != n.row) return row < n.row;
if(col != n.col) return col < n.col;
}
};
struct Heap{
Node heap[MAX_HEAP];
int size;
void reset(){
size = 0;
}
void swap(Node& a, Node& b){
Node c = a;
a = b;
b = c;
}
void up(int index){
int parent;
while(index){
parent = (index - 1) / 2;
if(heap[parent] > heap[index]) break;
swap(heap[parent], heap[index]);
index = parent;
}
}
void down(int index){
int left, right;
int largest;
while(1){
largest = index;
left = 2*largest + 1;
right = 2*largest + 2;
if(left < size && heap[left] > heap[largest]) largest = left;
if(right < size && heap[right] > heap[largest]) largest = right;
if(largest != index){
swap(heap[largest], heap[index]);
index = largest;
}
else break;
}
}
void push(Node n){
heap[size] = n;
size++;
up(size - 1);
}
Node pop(){
Node tmp = heap[0];
heap[0] = heap[size - 1];
size--;
down(0);
return tmp;
}
};
int abs(int x)
{
return (x < 0)? -x : x;
}
int distance(int rowA, int colA, int rowB, int colB)
{
return abs(rowA - rowB) + abs(colA - colB);
}
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
int map[MAX_N][MAX_N], visit[MAX_N][MAX_N];
int cntVisit, mapSize;
Bacteria bacteria[MAX_BACTERIAL];
Heap myHeap;
Result res;
void init(int N)
{
myHeap.reset();
cntVisit = 1;
mapSize = N;
for(int i = 0; i < mapSize; i++){
for(int j = 0; j < mapSize; j++){
map[i][j] = visit[i][j] = 0;
}
}
}
bool BFS(int row, int col, int mTime, int mId)
{
int curRow, curCol, nextRow, nextCol;
Node tmp;
int size = bacteria[mId].size;
int cnt = 0;
int dis;
tmp.setNode(row, col, 0);
myHeap.push(tmp);
/*visit[row][col] = cntVisit;
map[row][col] = mId;*/
while(myHeap.size){
tmp = myHeap.pop();
curRow = tmp.row;
curCol = tmp.col;
cnt++;
map[curRow][curCol] = mId;
if(cnt == size) {
res.row = curRow;
res.col = curCol;
return 1;
}
for(int i =0 ; i < 4; i++){
nextRow = curRow + dx[i];
nextCol = curCol + dy[i];
if(nextRow < 1 || nextRow > mapSize || nextCol < 1 || nextCol > mapSize || map[nextRow][nextCol] == mId) continue;
if(map[nextRow][nextCol] != 0 && bacteria[map[nextRow][nextCol]].time > mTime) continue;
dis = distance(row, col, nextRow, nextCol);
tmp.setNode(nextRow, nextCol, dis);
myHeap.push(tmp);
}
}
return 0;
}
Result putBacteria(int mTime, int mRow, int mCol, Bacteria mBac)
{
Result ret = { 0, 0 };
int idBac = map[mRow][mCol];
if(bacteria[idBac].time > mTime) return ret;
idBac = mBac.id;
bacteria[idBac].id = mBac.id;
bacteria[idBac].size = mBac.size;
bacteria[idBac].time = mBac.time + mTime;
if(BFS(mRow, mCol, mTime, idBac)) ret = res;
return ret;
}
int killBacteria(int mTime, int mRow, int mCol)
{
int idBac = map[mRow][mCol];
if(idBac != 0 && bacteria[idBac].time > mTime) {
bacteria[idBac].time = 0;
return idBac;
}
return 0;
}
int checkCell(int mTime, int mRow, int mCol)
{
int idBac = map[mRow][mCol];
if(idBac != 0 && bacteria[idBac].time > mTime) {
return idBac;
}
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
200
10000 20
20000 7 12 10 1 33 607 12 6
20000 13 15 10 2 17 1298 0 0
20000 20 14 3 3 29 1291 12 5
20000 28 6 11 4 62 649 5 6
20000 32 7 17 5 24 1609 4 18
20000 42 20 7 6 142 19840 11 17
20000 51 2 18 7 64 554 0 0
20000 56 6 20 8 40 535 0 0
20000 61 11 20 9 49 2620 0 0
20000 69 4 6 10 78 823 0 0
20000 72 7 16 11 47 2918 0 0
20000 74 3 6 12 73 1841 0 0
20000 75 2 1 13 79 2607 0 0
20000 83 7 6 14 34 1065 7 1
20000 84 12 19 15 14 1200 9 20
20000 91 3 1 16 47 1385 0 0
20000 99 1 13 17 72 355 0 0
20000 107 8 20 18 38 1749 0 0
20000 110 1 2 19 42 991 0 0
20000 120 5 2 20 78 531 0 0
20000 124 1 5 21 19 2083 3 2
20000 131 1 17 22 28 1382 0 0
20000 136 9 1 23 64 569 0 0
20000 146 8 20 24 50 374 0 0
20000 156 5 20 25 44 1997 0 0
20000 159 1 13 26 15 2118 1 20
20000 164 8 2 27 76 1290 0 0
20000 169 5 2 28 60 579 0 0
30000 173 4 1 0
20000 180 3 20 29 72 2012 0 0
20000 187 9 1 30 78 377 0 0
20000 197 9 1 31 23 2969 0 0
20000 203 8 1 32 35 866 0 0
20000 206 9 2 33 31 2620 0 0
20000 215 10 4 34 33 468 0 0
20000 221 8 1 35 27 2689 0 0
20000 230 9 3 36 76 346 0 0
20000 233 10 2 37 13 2047 0 0
20000 242 4 19 38 34 2495 0 0
20000 249 4 3 39 38 343 0 0
20000 253 3 1 40 58 1649 0 0
20000 259 8 1 41 45 2196 0 0
20000 260 10 2 42 60 2148 0 0
20000 267 11 1 43 66 613 0 0
20000 272 4 20 44 44 2374 0 0
20000 276 2 19 45 69 933 0 0
20000 277 9 1 46 24 643 0 0
20000 283 4 1 47 57 1830 0 0
20000 291 5 19 48 59 1458 0 0
20000 294 10 1 49 71 664 0 0
20000 295 9 2 50 60 2098 0 0
20000 299 4 1 51 78 2684 0 0
20000 300 4 3 52 60 1119 0 0
20000 310 8 1 53 53 2242 0 0
20000 312 8 20 54 59 2230 0 0
20000 318 4 20 55 32 745 0 0
20000 322 8 20 56 29 1543 0 0
20000 324 5 1 57 39 1572 0 0
20000 326 11 1 58 16 491 0 0
20000 336 5 2 59 12 563 0 0
20000 337 2 19 60 55 1536 0 0
20000 343 10 1 61 16 828 0 0
20000 351 11 5 62 80 19838 0 0
20000 355 10 4 63 57 2253 0 0
20000 364 4 2 64 28 2733 0 0
20000 374 11 5 65 43 2654 0 0
20000 384 9 2 66 67 1814 0 0
20000 387 11 1 67 31 2732 0 0
20000 389 5 2 68 53 228 0 0
20000 391 3 18 69 10 1372 6 20
20000 395 4 2 70 25 2196 0 0
30000 401 3 1 0
20000 405 10 1 71 38 2929 0 0
20000 406 9 1 72 27 1654 0 0
20000 407 8 1 73 42 2154 0 0
20000 415 10 4 74 31 1804 0 0
20000 417 11 1 75 27 1320 0 0
20000 425 8 2 76 57 1294 0 0
20000 430 9 2 77 69 2566 0 0
20000 432 8 20 78 58 2244 0 0
20000 440 10 4 79 74 2483 0 0
20000 442 8 20 80 14 2040 0 0
20000 446 9 2 81 33 824 0 0
20000 451 18 20 82 8 1553 0 0
20000 459 9 2 83 48 920 0 0
20000 465 8 1 84 62 788 0 0
20000 470 8 1 85 21 1091 0 0
20000 477 6 1 86 44 593 0 0
20000 487 10 2 87 11 456 0 0
40000 490 18 17 6
20000 494 5 2 88 74 458 0 0
20000 501 19 10 89 5 2740 0 0
20000 503 10 2 90 30 1608 0 0
20000 505 10 2 91 65 1575 0 0
20000 513 9 1 92 43 1377 0 0
40000 516 15 1 3
20000 522 11 1 93 77 1857 0 0
20000 526 4 1 94 56 786 0 0
20000 532 8 2 95 53 2333 0 0
20000 533 10 2 96 27 1276 0 0
20000 539 11 5 97 56 2527 0 0
20000 549 10 4 98 72 1532 0 0
20000 550 11 5 99 38 2530 0 0
20000 551 10 1 100 14 2042 0 0
20000 555 4 1 101 27 818 0 0
20000 558 9 3 102 66 344 0 0
20000 562 8 1 103 39 2473 0 0
20000 565 4 1 104 72 2164 0 0
20000 575 11 5 105 46 1685 0 0
20000 581 8 1 106 70 2799 0 0
20000 588 4 2 107 41 1716 0 0
20000 597 9 1 108 43 1765 0 0
20000 605 9 3 109 44 1562 0 0
20000 607 8 2 110 54 1993 0 0
20000 612 10 4 111 62 2672 0 0
20000 622 9 2 112 76 2163 0 0
20000 625 12 10 113 72 2658 0 0
20000 633 10 1 114 73 2402 0 0
20000 637 12 9 115 78 2982 0 0
20000 640 15 10 116 48 1665 0 0
20000 649 5 8 117 72 2305 0 0
20000 651 11 9 118 59 718 0 0
20000 659 11 12 119 29 2893 12 7
20000 664 5 1 120 68 2072 0 0
20000 673 9 2 121 33 1895 0 0
20000 683 4 9 122 14 1776 2 10
20000 689 9 12 123 59 284 0 0
20000 694 11 5 124 20 2972 0 0
20000 695 1 10 125 47 1696 8 14
20000 700 9 2 126 29 1291 0 0
20000 707 11 1 127 8 1035 9 3
20000 715 13 2 128 36 1490 0 0
20000 718 12 6 129 22 1516 0 0
20000 724 4 1 130 31 2552 0 0
20000 729 9 13 131 59 2706 0 0
20000 735 12 6 132 42 547 0 0
20000 745 14 9 133 67 2812 0 0
20000 749 13 8 134 57 695 0 0
20000 756 14 9 135 72 2857 0 0
20000 761 4 2 136 53 1234 0 0
20000 763 10 2 137 53 1686 0 0
20000 768 5 2 138 59 1404 0 0
20000 774 4 2 139 33 2292 0 0
20000 777 5 2 140 74 2486 0 0
20000 786 12 6 141 56 1697 0 0
20000 793 8 3 142 61 1868 0 0
20000 799 3 1 143 19 1091 0 0
20000 803 12 6 144 34 1453 0 0
20000 806 5 1 145 64 1006 0 0
20000 815 6 1 146 9 1371 0 0
20000 816 8 20 147 45 1285 0 0
20000 820 4 1 148 59 1687 0 0
20000 821 11 5 149 22 2186 0 0
20000 828 4 1 150 23 2407 0 0
20000 830 12 6 151 58 1181 0 0
20000 839 8 20 152 4 2514 0 0
20000 840 11 5 153 11 1718 0 0
20000 848 9 13 154 24 607 0 0
20000 856 13 8 155 16 727 0 0
20000 859 4 3 156 40 1728 0 0
20000 869 4 1 157 31 2739 0 0
20000 871 10 4 158 23 2577 0 0
20000 880 10 4 159 69 1710 0 0
20000 887 4 3 160 18 471 0 0
20000 891 5 2 161 14 1636 0 0
20000 901 12 6 162 62 367 0 0
20000 910 12 6 163 52 2238 0 0
20000 919 8 20 164 23 2689 0 0
20000 920 10 4 165 21 2330 0 0
20000 928 13 8 166 28 767 0 0
20000 937 3 1 167 17 901 0 0
20000 945 5 1 168 66 1221 0 0
20000 947 15 10 169 50 686 0 0
20000 954 4 3 170 76 895 0 0
20000 962 13 8 171 36 2763 0 0
20000 972 5 2 172 16 2684 0 0
20000 974 15 10 173 49 2959 0 0
30000 979 9 13 0
20000 986 9 13 174 5 2316 0 0
20000 995 12 6 175 15 2627 0 0
20000 996 4 3 176 35 670 0 0
20000 999 14 9 177 54 1281 0 0
20000 1002 3 1 178 16 473 0 0
20000 1011 15 10 179 31 290 0 0
20000 1020 6 1 180 66 2032 0 0
20000 1029 10 4 181 12 1010 0 0
20000 1039 15 10 182 24 1114 0 0
20000 1045 11 5 183 42 2258 0 0
20000 1051 5 1 184 74 1753 0 0
20000 1058 10 4 185 28 2304 0 0
20000 1067 10 4 186 65 1068 0 0
20000 1073 9 13 187 19 966 0 0
20000 1075 11 5 188 26 1015 0 0
20000 1079 3 1 189 37 2030 0 0
20000 1084 17 3 190 8 1478 0 0
20000 1088 8 20 191 34 1966 0 0
20000 1096 9 13 192 49 2443 0 0
20000 1100 5 1 193 70 2579 0 0
20000 1110 4 1 194 79 1491 0 0