Untitled
unknown
plain_text
20 days ago
10 kB
11
Indexable
Never
#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define MAXN 3001
#define MAXD 6001
#define MAXH 30001
unordered_set<int> rowmap[MAXN];
unordered_set<int> colmap[MAXN];
unordered_set<int> leftdiag[MAXD];
unordered_set<int> rightdiag[MAXD];
struct Hole
{
int row;
int col;
bool check;
int count;
};
Hole holes[MAXH];
struct Diagonal
{
int sr;
int er;
int sc;
int ec;
};
Diagonal leftdiagonal[MAXD];
Diagonal rightdiagonal[MAXD];
int gridsize;
int step;
void init(int N)
{
gridsize = N;
for (int i = 0; i < MAXN; i++) {
rowmap[i].clear();
colmap[i].clear();
}
for (int i = 0; i < MAXD; i++) {
leftdiag[i].clear();
rightdiag[i].clear();
}
for (int i = 0; i < MAXH; i++) {
holes[i].row = -1;
holes[i].col = -1;
holes[i].check = false;
holes[i].count = 0;
}
for (int i = 0; i < MAXD; i++) {
leftdiagonal[i].sr = -1;
leftdiagonal[i].sc = -1;
leftdiagonal[i].er = -1;
leftdiagonal[i].ec = -1;
rightdiagonal[i].sr = -1;
rightdiagonal[i].sc = -1;
rightdiagonal[i].er = -1;
rightdiagonal[i].ec = -1;
}
step = 0;
}
void addDiagonal(int mARow, int mACol, int mBRow, int mBCol)
{
if (mACol + mARow == mBCol + mBRow)
{
if (mARow < mBRow)
{
leftdiagonal[mARow + mACol].sr = mARow;
leftdiagonal[mARow + mACol].sc = mACol;
leftdiagonal[mARow + mACol].er = mBRow;
leftdiagonal[mARow + mACol].ec = mBCol;
}
else
{
leftdiagonal[mARow + mACol].sr = mBRow;
leftdiagonal[mARow + mACol].sc = mBCol;
leftdiagonal[mARow + mACol].er = mARow;
leftdiagonal[mARow + mACol].ec = mACol;
}
}
else
{
if (mARow < mBRow)
{
rightdiagonal[mARow - mACol + gridsize].sr = mARow;
rightdiagonal[mARow - mACol + gridsize].sc = mACol;
rightdiagonal[mARow - mACol + gridsize].er = mBRow;
rightdiagonal[mARow - mACol + gridsize].ec = mBCol;
}
else
{
rightdiagonal[mARow - mACol + gridsize].sr = mBRow;
rightdiagonal[mARow - mACol + gridsize].sc = mBCol;
rightdiagonal[mARow - mACol + gridsize].er = mARow;
rightdiagonal[mARow - mACol + gridsize].ec = mACol;
}
}
}
void addHole(int mRow, int mCol, int mID) {
holes[mID].row = mRow;
holes[mID].col = mCol;
holes[mID].check = true;
rowmap[mRow].emplace(mID);
colmap[mCol].emplace(mID);
leftdiag[mRow + mCol].emplace(mID);
rightdiag[mRow - mCol + gridsize].emplace(mID);
}
void eraseHole(int mRow, int mCol) {
for (auto it : rowmap[mRow])
{
if (holes[it].col == mCol)
{
holes[it].check = false;
break;
}
}
}
int hitMarble(int mRow, int mCol, int mK) {
step++;
int resHole = 0;
while (mK--)
{
int dist = 100000;
for (auto it : rowmap[mRow]) {
if (abs(holes[it].col - mCol) * 10 <= dist && (holes[it].check == true) && (holes[it].count < step)) {
if (abs(holes[it].col - mCol) * 10 < dist || holes[it].col < holes[resHole].col) {
dist = abs(holes[it].col - mCol) * 10;
resHole = it;
}
}
}
for (auto it : colmap[mCol]) {
if (abs(holes[it].row - mRow) * 10 <= dist && (holes[it].check == true) && (holes[it].count != step)) {
if (abs(holes[it].row - mRow) * 10 < dist || holes[it].row < holes[resHole].row) {
dist = abs(holes[it].row - mRow) * 10;
resHole = it;
}
}
}
if (mRow >= leftdiagonal[mRow + mCol].sr && mRow <= leftdiagonal[mRow + mCol].er) {
for (auto it : leftdiag[mRow + mCol]) {
if (holes[it].row >= leftdiagonal[mRow + mCol].sr && holes[it].row <= leftdiagonal[mRow + mCol].er) {
if (abs(holes[it].row - mRow) * 14 <= dist && (holes[it].check == true) && (holes[it].count != step)) {
if (abs(holes[it].row - mRow) * 14 < dist || holes[it].row < holes[resHole].row
|| (holes[it].row == holes[resHole].row && holes[it].col < holes[resHole].col))
{
dist = abs(holes[it].row - mRow) * 14;
resHole = it;
}
}
}
}
}
if(mRow >= rightdiagonal[mRow - mCol + gridsize].sr && mRow <= rightdiagonal[mRow - mCol + gridsize].er) {
for (auto it : rightdiag[mRow - mCol + gridsize]) {
if (holes[it].row >= rightdiagonal[mRow - mCol + gridsize].sr && holes[it].row <= rightdiagonal[mRow - mCol + gridsize].er) {
if (abs(holes[it].row - mRow) * 14 <= dist && (holes[it].check == true) && (holes[it].count != step)) {
if (abs(holes[it].row - mRow) * 14 < dist || holes[it].row < holes[resHole].row
|| (holes[it].row == holes[resHole].row && holes[it].col < holes[resHole].col))
{
dist = abs(holes[it].row - mRow) * 14;
resHole = it;
}
}
}
}
}
if (dist == 100000)
break;
else
{
holes[resHole].count = step;
mRow = holes[resHole].row;
mCol = holes[resHole].col;
}
}
if (resHole == 0)
return -1;
else return resHole;
}
/*
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
#include <iostream>
using namespace std;
extern void init(int N);
extern void addDiagonal(int mARow, int mACol, int mBRow, int mBCol);
extern void addHole(int mRow, int mCol, int mID);
extern void eraseHole(int mRow, int mCol);
extern int hitMarble(int mRow, int mCol, int mK);
/////////////////////////////////////////////////////////////////////////
#define CMD_INIT 0
#define CMD_DIAG 1
#define CMD_ADD 2
#define CMD_ERASE 3
#define CMD_HIT 4
static bool run()
{
int cmd, n, row, col, id, row1, col1, mk, ret;
int ans;
int Q = 0;
bool okay = false;
scanf("%d", &Q);
for (int q = 0; q < Q; ++q)
{
scanf("%d", &cmd);
switch (cmd)
{
case CMD_INIT:
scanf("%d", &n);
init(n);
okay = true;
break;
case CMD_DIAG:
scanf("%d %d %d %d", &row, &col, &row1, &col1);
addDiagonal(row, col, row1, col1);
break;
case CMD_ADD:
scanf("%d %d %d", &row, &col, &id);
addHole(row, col, id);
break;
case CMD_ERASE:
scanf("%d %d", &row, &col);
eraseHole(row, col);
break;
case CMD_HIT:
scanf("%d %d %d", &row, &col, &mk);
ret = hitMarble(row, col, mk);
scanf("%d", &ans);
if (ret != ans) {
cout<<ret<<" "<<ans<<endl;
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
31
0 9
4 5 5 5 -1
2 6 5 1
2 6 8 2
2 4 5 3
2 6 3 4
2 3 5 5
4 6 4 9 5
4 5 5 3 1
2 5 4 6
2 4 3 7
4 8 8 3 3
1 8 7 3 2
4 8 7 2 6
1 4 6 2 8
3 7 6
1 5 6 9 2
2 1 7 8
4 8 6 3 -1
2 9 6 9
2 7 1 10
4 4 1 5 5
2 9 2 11
2 2 8 12
2 2 2 13
4 8 3 7 9
1 5 2 9 6
4 8 5 4 6
3 5 4
4 6 7 4 5
4 3 7 4 3
200
0 20
2 18 16 1
2 3 15 2
2 14 4 3
2 15 10 4
2 17 17 5
1 18 12 14 8
4 16 20 3 -1
4 1 19 2 -1
1 7 15 2 10
2 19 6 6
2 16 4 7
2 2 9 8
3 8 17
4 3 10 1 2
2 19 8 9
2 5 10 10
4 2 2 1 8
2 1 2 11
4 15 20 3 10
3 16 14
2 13 5 12
4 11 18 3 -1
4 19 12 2 6
2 8 3 13
2 5 9 14
2 15 13 15
2 12 5 16
2 6 18 17
4 3 20 3 2
2 3 5 18
4 1 12 3 11
3 4 16
2 18 4 19
2 15 4 20
2 8 16 21
4 20 5 2 16
2 20 13 22
2 18 2 23
3 8 10
2 2 16 24
4 20 9 1 22
3 19 6
2 16 13 25
4 17 3 2 21
2 3 17 26
2 2 8 27
2 15 7 28
2 3 19 29
2 5 16 30
2 4 11 31
2 8 7 32
2 6 10 33
1 11 5 1 15
2 6 19 34
2 12 15 35
2 10 3 36
4 20 3 3 32
2 17 10 37
4 19 3 3 8
2 1 3 38
2 20 11 39
2 8 13 40
2 12 19 41
1 3 13 1 11
4 10 2 3 32
2 18 3 42
2 16 8 43
2 11 9 44
2 3 12 45
3 15 10
4 19 18 1 9
2 3 3 46
2 20 2 47
2 5 7 48
2 1 12 49
2 7 20 50
2 10 20 51
2 14 17 52
2 12 1 53
2 16 11 54
2 4 1 55
1 3 4 1 6
2 12 9 56
2 3 9 57
2 9 18 58
2 15 9 59
2 7 7 60
2 1 6 61
2 16 20 62
2 14 5 63
4 19 16 2 21
2 9 19 64
2 14 10 65
3 14 10
2 16 1 66
1 19 3 20 4
2 13 16 67
2 19 1 68
4 16 6 1 7
4 6 5 1 18
4 20 7 2 22
4 18 9 2 28
1 18 1 3 16
2 15 8 69
2 5 11 70
4 13 6 3 63
4 5 18 3 29
2 17 15 71
2 14 20 72
2 4 8 73
4 5 1 1 55
3 4 14
2 5 6 74
2 2 3 75
2 17 7 76
3 9 5
4 3 2 1 46
4 7 9 1 33
4 3 6 2 46
4 1 14 1 49
2 2 12 77
4 19 2 1 23
3 19 6
2 11 17 78
2 7 18 79
2 11 14 80
2 14 19 81
2 5 15 82
2 19 9 83
4 14 9 2 69
2 6 20 84
4 14 7 2 69
1 13 2 12 1
2 10 9 85
2 9 12 86
2 9 3 87
2 9 7 88
1 8 9 1 16
2 15 15 89
2 18 15 90
2 19 16 91
2 19 2 92
4 7 1 3 27
4 16 17 1 5
2 12 2 93
4 14 11 3 15
2 8 8 94
4 17 14 3 1
2 20 7 95
2 4 15 96
4 12 13 1 35
4 9 14 3 32
3 18 16
2 13 2 97
2 3 11 98
2 7 9 99
4 10 11 2 44
2 7 5 100
2 3 2 101
2 11 6 102
2 12 10 103
3 15 13
2 20 8 104
4 5 14 3 2
2 9 16 105
2 15 14 106
1 1 2 2 1
2 7 17 107
4 13 20 3 41
2 14 18 108
4 10 15 2 89
2 14 8 109
4 19 10 1 83
4 19 6 1 9
4 15 1 1 66
2 18 9 110
3 7 1
4 13 14 3 52
2 3 6 111
4 17 14 3 89
2 19 5 112
2 11 18 113
2 2 14 114
2 8 4 115
3 8 11
2 12 6 116
2 13 14 117
2 19 12 118
2 8 14 119
2 8 20 120
4 3 7 2 18
4 4 9 3 27
2 7 2 121
4 4 2 2 46
4 19 10 3 59
2 14 16 122
2 17 1 123
4 12 11 3 44
4 13 19 3 108
*/Leave a Comment