Submission #1101303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101303		anhphant	Cell Automaton (JOI23_cell)	C++14	16 / 100	257 ms	266056 KiB

cell

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define dot cerr << "passed" << '\n';
#define debug(x) cerr << "debug : " << #x << " = " << x << '\n';

ll N, Q;
pair<ll, ll> A[100007];
struct query {
	ll t, id;
};
query Queries[500007];
ll ans[500007];

namespace subtask1 {
	ll Cnt[57], cell[2][507][507];
	const ll offset = 157;

	void solve() {
		for(int i = 1; i <= N; ++i) {
			cell[0][A[i].fi + offset][A[i].se + offset] = 1;
		}
		auto fill = [&](ll p, ll a, ll b, ll c, ll d) {
			if (cell[p][c][d] == -1) return; // grey can't fill
			if (cell[p][c][d] == 1) return; // black can't fill
			cell[(p + 1) % 2][c][d] = 1; // white near black -> fill
		};	
		// dot;
		for(int tm = 0; tm <= 500; ++tm) { // tm fix
			memset(cell[(tm + 1) % 2], 0, sizeof(cell[(tm + 1) % 2]));
			for(int i = 1; i <= 500; ++i) {
				for(int j = 1; j <= 500; ++j) {
					// 1 : black
					// -1 : grey
					// 0 : white
					if (cell[tm % 2][i][j] == 1) {
						Cnt[tm]++;
						fill(tm % 2, i, j, i - 1, j);
						fill(tm % 2, i, j, i, j - 1);
						fill(tm % 2, i, j, i + 1, j);
						fill(tm % 2, i, j, i, j + 1);
						cell[(tm + 1) % 2][i][j] = -1; // its grey now
					}
				}
			}
			// cerr << "print table " << '\n';
			// for(int i = -5 + offset; i <= 5 + offset; ++i) {
			// 	for(int j = -5 + offset; j <= 5 + offset; ++j) {
			// 		if (cell[tm % 2][i][j] == -1) cerr << 2;
			// 		else cerr << cell[tm % 2][i][j];
			// 	}
			// 	cerr << '\n';
			// }
			// cerr << '\n';
		}
		for(int i = 1; i <= Q; ++i) {
			// cerr << "query " << i << '\n';
			cout << Cnt[Queries[i].t] << '\n';
		}
	}

	void process() {
		solve();
	}
}

namespace subtask2 {
	ll dist[4007][4007];
	const ll dx[4] = {-1, 0, 0, 1};
	const ll dy[4] = {0, -1, 1, 0};
	const ll os = 2002;
	ll Cnt[1007];

	void solve() {
		for(int i = 0; i <= 4002; ++i) fill(dist[i], dist[i] + 4003, 1e18);
		queue<pair<ll, ll>> qu;
		for(int i = 1; i <= N; ++i) {
			dist[A[i].fi + os][A[i].se + os] = 0;
			qu.push({A[i].fi, A[i].se});
		}
		while(!qu.empty()) {
			auto [x, y] = qu.front();
			qu.pop();
			if (dist[x + os][y + os] == 1000) break;
			Cnt[dist[x + os][y + os]]++;
			for(int id = 0; id < 4; ++id) {
				ll x2 = x + dx[id];
				ll y2 = y + dy[id];
				if (dist[x2 + os][y2 + os] != 1e18) continue;
				dist[x2 + os][y2 + os] = dist[x + os][y + os] + 1;
				qu.push({x2, y2});
			}
		}

		for(int i = 1; i <= Q; ++i) {
			cout << Cnt[Queries[i].t] << '\n';
		}
	}

	void process() {
		solve();
	}
}

int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0); cerr.tie(0);
	if (fopen("FILE.INP", "r")) {
		freopen("FILE.INP", "r", stdin);
		freopen("FILE.OUT", "w", stdout);
	}

	cin >> N >> Q;
	for(int i = 1; i <= N; ++i) cin >> A[i].fi >> A[i].se;
	for(int i = 1; i <= Q; ++i) {
		cin >> Queries[i].t;
		Queries[i].id = i;
	}

	subtask2 :: process();
}

Compilation message (stderr)

cell.cpp: In function 'void subtask2::solve()':
cell.cpp:84:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |    auto [x, y] = qu.front();
      |         ^
cell.cpp: In function 'int main()':
cell.cpp:111:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   freopen("FILE.INP", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cell.cpp:112:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   freopen("FILE.OUT", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 0 / 8
• Subtask 4: 0 / 8
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 26