QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#344621#2476. Pizzo CollectorsPetroTarnavskyi#TL 0ms0kbC++205.4kb2024-03-04 20:32:352024-03-04 20:32:35

Judging History

你现在查看的是最新测评结果

  • [2024-03-04 20:32:35]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-03-04 20:32:35]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int N = 55;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

const vector<PII> knightMoves = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};

int n;
string s[N];
bool illuminated[N][N];
bool g[N][N]; // for dfs
int flockIdx[N][N];
int connectedToBorder[N][N];
int width[N * N];

bool ok(int i, int j)
{
	return 0 <= i && i < n && 0 <= j && j < n;
}

void dfs(int i, int j, int used[N][N])
{
	FOR(k, 0, 4)
	{
		int ni = i + dx[k], nj = j + dy[k];
		if (ok(ni, nj) && g[ni][nj] && used[ni][nj] == -1)
		{
			used[ni][nj] = used[i][j];
			dfs(ni, nj, used);
		}
	}
}

void calcWidth(int i, int j, int di, int dj)
{
	int w = 0;
	while (ok(i, j))
	{
		int fl = flockIdx[i][j];
		if (fl == -1)
			w = 0;
		else
		{
			w++;
			width[fl] = max(width[fl], w);
		}
		i += di;
		j += dj;
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	getline(cin, s[0]);
	FOR(i, 0, n)
		getline(cin, s[i]);
	LL ans = 0;
	// suns
	FOR(i, 0, n)
	{
		FOR(j, 0, n)
		{
			FOR(di, -1, 2)
			{
				FOR(dj, -1, 2)
				{
					int r = i + di, c = j + dj;
					while (ok(r, c) && s[r][c] == ' ')
					{
						r += di;
						c += dj;
					}
					if (ok(r, c) && s[r][c] != '*')
						illuminated[r][c] = true;
				}
			}
		}
	}
	FOR(i, 0, n)
		FOR(j, 0, n)
			if (illuminated[i][j])
				ans += 100;
	// birds
	FOR(i, 0, n)
		FOR(j, 0, n)
		{
			flockIdx[i][j] = -1;
			g[i][j] = s[i][j] == 'v' || s[i][j] == 'D';
		}
	int flocks = 0;
	FOR(i, 0, n)
	{
		FOR(j, 0, n)
		{
			if (g[i][j] && flockIdx[i][j] == -1)
			{
				flockIdx[i][j] = flocks++;
				dfs(i, j, flockIdx);
			}
		}
	}
	FOR(i, 0, n)
	{
		// horizontal
		calcWidth(i, 0, 0, 1);
		// vertical
		calcWidth(0, i, 1, 0);
		// diagonal
		calcWidth(i, 0, 1, 1);
		calcWidth(0, i, 1, 1);
		calcWidth(i, 0, -1, 1);
		calcWidth(n - 1, i, -1, 1);
	}
	FOR(i, 0, flocks)
		ans += 500 * width[i];
	// flock perimeter
	FOR(i, 0, n)
	{
		FOR(j, 0, n)
		{
			if (g[i][j])
			{
				FOR(k, 0, 4)
				{
					int ni = i + dx[k], nj = j + dy[k];
					if (!ok(ni, nj) || !g[ni][nj])
						ans += 60;
				}
			}
		}
	}
	#warning
	// house view up and down
	FOR(i, 0, n)
	{
		FOR(j, 0, n)
		{
			if (s[i][j] == '^')
			{
				// up
				for (int k = i - 1; k >= 0 && s[k][j] == ' '; k--)
				{
					ans += 10;
				}
				// down
				for (int k = i + 1; k < n && s[k][j] == ' '; k++)
				{
					ans += 5;
				}
			}
		}
	}
	// 3x3 blocks
	set<string> uniqueBlocks;
	FOR(i, 0, n - 2)
	{
		FOR(j, 0, n - 2)
		{
			string t;
			FOR(ii, i, i + 3)
			{
				FOR(jj, j, j + 3)
				{
					t += s[ii][jj];
				}
			}
			uniqueBlocks.insert(t);
		}
	}
	ans += SZ(uniqueBlocks);
	// animals i
	FOR(i, 0, n)
	{
		FOR(j, 0, n)
		{
			if (s[i][j] != '!' && s[i][j] != 'v' && s[i][j] != 'D')
			{
				continue;
			}
			FOR(k, 0, 4)
			{
				int ni = i + dx[k], nj = j + dy[k];
				if (ok(ni, nj) && s[ni][nj] == ' ')
					ans += 15;
			}
		}
	}
	// freedom
	FOR(i, 0, n)
		FOR(j, 0, n)
			g[i][j] = (i == 0 || i == n - 1 || j == 0 || j == n - 1) && s[i][j] == ' ';
	FOR(i, 0, n)
		FOR(j, 0, n)
			if (g[i][j] && connectedToBorder[i][j] == 0)
			{
				connectedToBorder[i][j] = 1;
				dfs(i, j, connectedToBorder);
			}
	FOR(i, 0, n)
		FOR(j, 0, n)
		{
			if (s[i][j] == ' ')
				continue;
			bool freedom = false;
			FOR(k, 0, 4)
			{
				int ni = i + dx[k], nj = j + dy[k];
				freedom |= ok(ni, nj) && connectedToBorder[ni][nj];
			}
			if (freedom)
			{
				ans += 7;
			}
		}
	// chupakabra
	FOR(i, 0, n)
	{
		FOR(j, 0, n)
		{
			if (s[i][j] != 'v' && s[i][j] != 'B')
			{
				continue;
			}
			bool can = false;
			for (auto [kdx, kdy] : knightMoves)
			{
				int ni = i + kdx, nj = j + kdy;
				can |= ok(ni, nj) && s[ni][nj] == '!';
			}
			if (can)
				ans += 200;
		}
	}
	// peaks
	vector<PII> peaks;
	FOR(i, 0, n)
		FOR(j, 0, n - 1)
		{
			if (s[i][j] == '/' && s[i][j] == '\\')
				peaks.PB({i, j});
		}
	for (auto [i1, j1] : peaks)
	{
		int mx = 0;
		for (auto [i2, j2] : peaks)
		{
			int d = abs(i2 - i1) + abs(j2 - j1);
			if (d != 0)
				mx = max(mx, d);
		}
		ans += 50 * mx;
	}
	vector<tuple<char, char, int>> drakeGrill = {{'D', 'G', 500}, {'G', 'D', 50}};
	// drake/grill and grill/drake
	for (auto [c1, c2, score] : drakeGrill)
	{
		FOR(i, 0, n)
		{
			FOR(j, 0, n)
			{
				if (s[i][j] != c1)
					continue;
				bool can = false;
				FOR(k, 0, 4)
				{
					int ni = i + dx[k], nj = j + dy[k];
					can |= ok(ni, nj) && s[ni][nj] == 'G';
				}
				if (can)
					ans += score;
			}
		}
	}
	map<char, int> cnt;
	// minimum frequency
	FOR(i, 0, n)
	{
		FOR(j, 0, n)
		{
			cnt[s[i][j]]++;
		}
	}
	int mn = n * n + 1;
	for (auto [c, cn] : cnt)
		if (c != ' ')
			mn = min(mn, cn);
	if (mn <= n * n)
		ans += 10 * mn;
	// empty fields
	ans += cnt[' '];
	// animals ii
	ans += (LL)cnt['!'] * cnt['b'] * cnt['D'];
	ans += 3 * min(cnt['^'], cnt['G']);
	cout << ans << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

8
?A?B?A?C
3
A 1
B 1000
C 100000

output:


result: