/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 6ms 320.0 KiB
#2 Accepted 3ms 532.0 KiB
#3 Accepted 9ms 352.0 KiB
#4 Accepted 4ms 532.0 KiB
#5 Accepted 7ms 324.0 KiB
#6 Accepted 11ms 560.0 KiB
#7 Accepted 9ms 532.0 KiB
#8 Accepted 13ms 532.0 KiB
#9 Accepted 22ms 500.0 KiB
#10 Accepted 9ms 532.0 KiB
#11 Accepted 16ms 532.0 KiB
#12 Accepted 10ms 764.0 KiB
#13 Accepted 10ms 560.0 KiB
#14 Accepted 15ms 532.0 KiB
#15 Accepted 9ms 560.0 KiB
#16 Accepted 8ms 532.0 KiB
#17 Accepted 8ms 556.0 KiB
#18 Accepted 26ms 532.0 KiB
#19 Accepted 5ms 532.0 KiB
#20 Accepted 3ms 532.0 KiB
#21 Accepted 3ms 324.0 KiB
#22 Accepted 12ms 532.0 KiB
#23 Accepted 9ms 320.0 KiB
#24 Accepted 6ms 536.0 KiB
#25 Accepted 15ms 532.0 KiB
#26 Accepted 12ms 324.0 KiB
#27 Accepted 10ms 532.0 KiB
#28 Accepted 14ms 532.0 KiB
#29 Accepted 16ms 340.0 KiB
#30 Accepted 12ms 544.0 KiB
#31 Accepted 11ms 560.0 KiB
#32 Accepted 10ms 532.0 KiB
#33 Accepted 11ms 532.0 KiB
#34 Accepted 12ms 532.0 KiB
#35 Accepted 10ms 532.0 KiB
#36 Accepted 29ms 532.0 KiB
#37 Accepted 23ms 556.0 KiB
#38 Accepted 4ms 320.0 KiB
#39 Accepted 4ms 532.0 KiB
#40 Accepted 3ms 532.0 KiB
#41 Accepted 3ms 376.0 KiB
#42 Accepted 4ms 500.0 KiB
#43 Accepted 3ms 480.0 KiB
#44 Accepted 4ms 508.0 KiB
#45 Accepted 3ms 532.0 KiB
#46 Accepted 4ms 764.0 KiB
#47 Accepted 12ms 532.0 KiB
#48 Accepted 5ms 536.0 KiB
#49 Accepted 5ms 532.0 KiB
#50 Accepted 6ms 500.0 KiB
#51 Accepted 9ms 560.0 KiB
#52 Accepted 13ms 532.0 KiB
#53 Accepted 9ms 532.0 KiB
#54 Accepted 54ms 532.0 KiB
#55 Accepted 3ms 532.0 KiB
#56 Accepted 4ms 532.0 KiB
#57 Accepted 13ms 556.0 KiB
#58 Accepted 4ms 532.0 KiB
#59 Accepted 3ms 528.0 KiB
#60 Accepted 303ms 556.0 KiB
#61 Accepted 3ms 532.0 KiB
#62 Accepted 3ms 532.0 KiB
#63 Accepted 4ms 532.0 KiB
#64 Accepted 5ms 336.0 KiB
#65 Accepted 10ms 552.0 KiB
#66 Accepted 3ms 532.0 KiB
#67 Accepted 5ms 532.0 KiB
#68 Accepted 35ms 552.0 KiB
#69 Accepted 5ms 532.0 KiB
#70 Accepted 5ms 564.0 KiB
#71 Accepted 5ms 532.0 KiB
#72 Accepted 51ms 560.0 KiB
#73 Accepted 5ms 532.0 KiB
#74 Accepted 4ms 320.0 KiB
#75 Accepted 9ms 552.0 KiB
#76 Accepted 9ms 532.0 KiB
#77 Accepted 5ms 568.0 KiB
#78 Accepted 4ms 564.0 KiB
#79 Accepted 6ms 532.0 KiB
#80 Accepted 4ms 532.0 KiB
#81 Accepted 99ms 560.0 KiB
#82 Accepted 7ms 532.0 KiB
#83 Accepted 19ms 532.0 KiB
#84 Accepted 5ms 532.0 KiB
#85 Accepted 63ms 556.0 KiB
#86 Accepted 9ms 320.0 KiB
#87 Accepted 74ms 564.0 KiB
#88 Accepted 21ms 532.0 KiB
#89 Accepted 3ms 532.0 KiB
#90 Accepted 290ms 564.0 KiB
#91 Wrong Answer 3ms 320.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];
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;
}

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;
pre = -1;
do {
	if (perm[u] == pre) continue;
	u = get();
	pre = perm[u];
	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:06:03
Judged At
2026-01-06 16:06:03
Judged By
Score
90
Total Time
303ms
Peak Memory
764.0 KiB