/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 7ms 532.0 KiB
#2 Accepted 3ms 532.0 KiB
#3 Accepted 8ms 532.0 KiB
#4 Accepted 4ms 328.0 KiB
#5 Accepted 4ms 532.0 KiB
#6 Accepted 5ms 532.0 KiB
#7 Accepted 5ms 532.0 KiB
#8 Accepted 10ms 532.0 KiB
#9 Accepted 16ms 536.0 KiB
#10 Accepted 7ms 568.0 KiB
#11 Accepted 14ms 532.0 KiB
#12 Accepted 10ms 532.0 KiB
#13 Accepted 14ms 532.0 KiB
#14 Accepted 18ms 532.0 KiB
#15 Accepted 7ms 560.0 KiB
#16 Accepted 6ms 560.0 KiB
#17 Accepted 7ms 320.0 KiB
#18 Accepted 30ms 532.0 KiB
#19 Accepted 11ms 532.0 KiB
#20 Accepted 7ms 324.0 KiB
#21 Accepted 7ms 532.0 KiB
#22 Accepted 16ms 556.0 KiB
#23 Accepted 12ms 324.0 KiB
#24 Accepted 9ms 556.0 KiB
#25 Accepted 17ms 532.0 KiB
#26 Accepted 14ms 532.0 KiB
#27 Accepted 13ms 480.0 KiB
#28 Accepted 11ms 532.0 KiB
#29 Accepted 15ms 532.0 KiB
#30 Accepted 13ms 532.0 KiB
#31 Accepted 13ms 324.0 KiB
#32 Accepted 12ms 532.0 KiB
#33 Accepted 13ms 560.0 KiB
#34 Accepted 13ms 532.0 KiB
#35 Accepted 5ms 532.0 KiB
#36 Accepted 14ms 532.0 KiB
#37 Accepted 22ms 532.0 KiB
#38 Accepted 6ms 532.0 KiB
#39 Accepted 7ms 532.0 KiB
#40 Accepted 8ms 560.0 KiB
#41 Accepted 9ms 320.0 KiB
#42 Accepted 13ms 532.0 KiB
#43 Accepted 11ms 440.0 KiB
#44 Accepted 14ms 532.0 KiB
#45 Accepted 12ms 532.0 KiB
#46 Accepted 13ms 320.0 KiB
#47 Accepted 29ms 532.0 KiB
#48 Accepted 7ms 532.0 KiB
#49 Accepted 6ms 536.0 KiB
#50 Accepted 7ms 532.0 KiB
#51 Accepted 16ms 532.0 KiB
#52 Accepted 21ms 532.0 KiB
#53 Accepted 16ms 320.0 KiB
#54 Accepted 54ms 560.0 KiB
#55 Accepted 4ms 532.0 KiB
#56 Accepted 5ms 532.0 KiB
#57 Accepted 24ms 532.0 KiB
#58 Accepted 8ms 532.0 KiB
#59 Accepted 6ms 532.0 KiB
#60 Accepted 314ms 556.0 KiB
#61 Accepted 4ms 532.0 KiB
#62 Accepted 3ms 532.0 KiB
#63 Accepted 4ms 564.0 KiB
#64 Accepted 5ms 532.0 KiB
#65 Accepted 10ms 532.0 KiB
#66 Accepted 4ms 532.0 KiB
#67 Accepted 6ms 564.0 KiB
#68 Accepted 28ms 532.0 KiB
#69 Accepted 5ms 532.0 KiB
#70 Accepted 7ms 532.0 KiB
#71 Accepted 11ms 532.0 KiB
#72 Accepted 63ms 532.0 KiB
#73 Accepted 6ms 532.0 KiB
#74 Accepted 5ms 532.0 KiB
#75 Accepted 12ms 364.0 KiB
#76 Accepted 14ms 532.0 KiB
#77 Accepted 9ms 564.0 KiB
#78 Accepted 8ms 560.0 KiB
#79 Accepted 11ms 532.0 KiB
#80 Accepted 8ms 532.0 KiB
#81 Accepted 109ms 560.0 KiB
#82 Accepted 8ms 532.0 KiB
#83 Accepted 19ms 564.0 KiB
#84 Accepted 7ms 532.0 KiB
#85 Accepted 78ms 552.0 KiB
#86 Accepted 10ms 320.0 KiB
#87 Accepted 74ms 532.0 KiB
#88 Accepted 22ms 532.0 KiB
#89 Accepted 4ms 532.0 KiB
#90 Accepted 288ms 552.0 KiB
#91 Wrong Answer 3ms 532.0 KiB
#92 Wrong Answer 3ms 532.0 KiB

Code

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int N = 1000005;
bool DEBUG = true;

int i, j, d, maxx, perm[9], tab[11][11], bat[11][11], dist[11][11], u, pre;
ii pers[9];
VI vv;
string s;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {-1, 1, 0, 0};

bool ok(int a, int b) {
	return a >=0 && a <= 10 && b >=0 && b <= 10;
}

void spread(int u) {
	queue<ii> q;
	for (int i=0;i<11;i++) for (int j=0;j<11;j++) if (bat[i][j]) {
		q.push(ii(i, j));
		dist[i][j] = 0;
	} else dist[i][j] = -1;
	while (!q.empty()) {
		ii w = q.front();
		q.pop();
		for (int k=0;k<4;k++) if (ok(w.first + dx[k], w.second + dy[k]) && dist[w.first + dx[k]][w.second + dy[k]] == -1) {
			q.push(ii(w.first + dx[k], w.second + dy[k]));
			dist[w.first + dx[k]][w.second + dy[k]] = dist[w.first][w.second] + 1;
		}
	}
	for (int i=0;i<11;i++) for (int j=0;j<11;j++) bat[i][j] = dist[i][j] <= u;
}

bool canLeft(int x, int y) {
	int d = 0;
	while (x > 0) {
		x--;
		d++;
		for (int i=max(0, y - d);i<=min(10, y + d);i++) if (bat[x][i]) return false;
	}
	return true;
}

bool canRight(int x, int y) {
	int d = 0;
	while (x < 10) {
		x++;
		d++;
		for (int i=max(0, y - d);i<=min(10, y + d);i++) if (bat[x][i]) return false;
	}
	return true;
}

bool canUp(int x, int y) {
	int d = 0;
	while (y > 0) {
		y--;
		d++;
		for (int i=max(0, x - d);i<=min(10, x + d);i++) if (bat[i][y]) return false;
	}
	return true;
}

bool canDown(int x, int y) {
	int d = 0;
	while (y < 10) {
		y++;
		d++;
		for (int i=max(0, x - d);i<=min(10, x + d);i++) if (bat[i][y]) return false;
	}
	return true;
}

int tim(int ind) {
	int x = pers[ind].first;
	int y = pers[ind].second;
	if (bat[x][y]) return INF;
	int res = INF;
	if (x + 1 < res && canLeft(x, y)) res = x + 1;
	if (11 - x < res && canRight(x, y)) res = 11 - x;
	if (y + 1 < res && canUp(x, y)) res = y + 1;
	if (11 - y < res && canDown(x, y)) res = 11 - y;
	return res;
}

int get() {
	for (int i=0;i<11;i++) for (int j=0;j<11;j++) bat[i][j] = tab[i][j];
	for (int i=0;i<9;i++) {
		int u = tim(perm[i]);
		
		if (u == INF) return i;
		spread(u);
		/*if (DEBUG) {
			cout << u << endl;
			for (int j=0;j<11;j++) {
				for (int k=0;k<11;k++) cout << dist[j][k];
				cout << endl;
			}
		}*/
	}
	return 9;
}

bool same() {
	for (int i=0;i<vv.size();i++) if (perm[i] != vv[i]) return false;
	return true;
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

d = 0;
for (i=0;i<11;i++) for (j=0;j<11;j++) {
	cin >> s;
	if (s[0] == 'F') tab[i][j] = 1; else if (s[0] == 'P') pers[d++] = ii(i, j);
}
maxx = 0;
for (i=0;i<9;i++) perm[i] = i;
u = 0;
vv.pb(-1);
do {
	if (same()) continue;
	u = get();
	vv.clear();
	for (i=0;i<=min(8, u);i++) vv.pb(perm[i]);
	maxx = max(maxx, u);
} while (maxx < 9 && next_permutation(perm, perm + 9));
cout << maxx << endl;
return 0;
}

Information

Submit By
Type
Submission
Problem
P1221 G. Nine-eleven
Contest
Happy New Year 2026
Language
C++17 (G++ 13.2.0)
Submit At
2026-01-06 16:18:18
Judged At
2026-01-06 16:18:18
Judged By
Score
90
Total Time
314ms
Peak Memory
568.0 KiB