QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#952209#10243. Opieka [A]zlt0 410ms54008kbC++143.4kb2025-03-26 21:06:112025-03-26 21:06:18

Judging History

This is the latest submission verdict.

  • [2025-03-26 21:06:18]
  • Judged
  • Verdict: 0
  • Time: 410ms
  • Memory: 54008kb
  • [2025-03-26 21:06:11]
  • Submitted

answer

// Problem: P11921 [PA 2025] 看护 / Opieka
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P11921
// Memory Limit: 1 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 100100;

int n, m, a[19][maxn], b[maxn], nxt[19][maxn], c[19][maxn], g[19][maxn];
pii fr[maxn << 5];
char s[19][maxn];

int p[19];
ll X, Y, f[19];

bool dfs(int d, int S) {
	if (d == n + 1) {
		return 1;
	}
	vector<int> cur;
	for (int i = 1; i <= n; ++i) {
		if (!(S & (1 << i))) {
			cur.pb(i);
		}
	}
	pii mn(1e18, 0), smn(1e18, 0);
	for (int i : cur) {
		ll t = f[d - 1];
		for (int j = 1; j <= d; ++j) {
			ll l = max(f[d - 1], j == 1 ? 0LL : f[j - 1] + X), r = (j < d ? f[j] + X : m * Y);
			if (l < r) {
				if (j == 1 && d - j + 2 == n + 1) {
					t = max(t, r);
					continue;
				}
				if (g[d - j + 2][l / Y + 1] >= (l + X + Y - 1) / Y - l / Y) {
					t = max(t, l);
				} else {
					t = max(t, min(r, (nxt[d - j + 2][l / Y + 2] - 1) * Y));
				}
			}
		}
		if (t % Y) {
			if (a[i][t / Y + 1] >= (t + X + Y - 1) / Y - t / Y) {
				pii x(t, i);
				if (x < mn) {
					smn = mn;
					mn = x;
				} else if (x < smn) {
					smn = x;
				}
				continue;
			} else {
				t += Y - t % Y;
			}
		}
		t = (c[i][t / Y + 1] - 1) * Y;
		if (t == m * Y) {
			return 0;
		}
		pii x(t, i);
		if (x < mn) {
			smn = mn;
			mn = x;
		} else if (x < smn) {
			smn = x;
		}
	}
	f[d] = mn.fst;
	p[d] = mn.scd;
	if (dfs(d + 1, S | (1 << mn.scd))) {
		return 1;
	}
	if (smn.scd) {
		f[d] = smn.fst;
		p[d] = smn.scd;
		if (dfs(d + 1, S | (1 << smn.scd))) {
			return 1;
		}
	}
	return 0;
}

inline bool check(ll x, ll y) {
	for (int i = 1; i <= n; ++i) {
		c[i][m + 1] = m + 1;
		for (int j = m; j; --j) {
			c[i][j] = (a[i][j] * y >= x ? j : c[i][j + 1]);
		}
	}
	for (int i = 1; i <= n; ++i) {
		nxt[i][m + 1] = m + 1;
		for (int j = m; j; --j) {
			g[i][j] = (b[j] >= i ? g[i][j + 1] + 1 : 0);
			nxt[i][j] = (g[i][j] * y >= x ? j : nxt[i][j + 1]);
		}
	}
	X = x;
	Y = y;
	f[0] = 0;
	return dfs(1, 0);
}

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%s", s[i] + 1);
	}
	for (int i = 1; i <= m; ++i) {
		bool fl = 1;
		for (int j = 1; j <= n && fl; ++j) {
			fl &= (s[j][i] == 'X');
		}
		if (fl) {
			puts("-1");
			return;
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = m; j; --j) {
			a[i][j] = (s[i][j] == '.' ? a[i][j + 1] + 1 : 0);
			b[j] += (s[i][j] == '.');
		}
	}
	int tot = 0;
	for (int i = 1; i <= m; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (__gcd(i, j) == 1) {
				fr[++tot] = mkp(i, j);
			}
		}
	}
	sort(fr + 1, fr + tot + 1, [&](const pii &a, const pii &b) {
		return a.fst * b.scd < b.fst * a.scd;
	});
	int l = 1, r = tot, ans = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(fr[mid].fst, fr[mid].scd)) {
			ans = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	if (ans == -1) {
		puts("0/1");
		return;
	}
	printf("%lld/%lld\n", fr[ans].fst, fr[ans].scd);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 1
Accepted
time: 0ms
memory: 10076kb

input:

1 1
.

output:

0/1

result:

ok single line: '0/1'

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 16276kb

input:

5 100
....X..XXX........X.XX.X...............XX..............X....................X.....X.........XXXX.XX.
....X..X..........X.X..........X...................................X.......X..X.........X.....X....X
....X..X.....X....X.X.X................XX................X..X..................................

output:

71/4

result:

wrong answer 1st lines differ - expected: '73/4', found: '71/4'

Subtask #2:

score: 0
Wrong Answer

Test #36:

score: 1
Accepted
time: 0ms
memory: 14292kb

input:

6 1000
...XXXX.XXX..XXX......XX.XX..XXX....X...XX.X...XXXX.X.....XX.XX...XX..X.X...X..XXXXX.X...X.X.XX.XX..X........X....XXX.X..XXXXX.XX.X..X....XX..X...XXX..XXX..X.XX..X.X...XXXXX.XXXXXXX.XX..XX.X...X.XXXX.XXX..X...X.X.XX...XXX.XXX.X..X...X..XX.X....XXX.X.X.XXXX...X..XX.....X.X..XX.XX.X.XX..XX...XX...

output:

6/1

result:

ok single line: '6/1'

Test #37:

score: 1
Accepted
time: 1ms
memory: 20404kb

input:

6 1000
.X.................................XX..XXXX.X........X...................................................XX.X..X...X.X.........X.........X........X.................X...............................................................................................X..................XX......X........

output:

78/1

result:

ok single line: '78/1'

Test #38:

score: 1
Accepted
time: 0ms
memory: 14244kb

input:

6 1000
..XXX.........X...XXX.........X........X..........................X..........XX...X...........XX...X.................X...........................................X.......................X.XX...................X.XXXXXX...............XXXXXXXXXXXXXXXXXXXXXXXXXXXXX....................................

output:

155/2

result:

ok single line: '155/2'

Test #39:

score: 0
Wrong Answer
time: 1ms
memory: 18332kb

input:

6 997
.....X....XX........XX.........................................XX.X..............XXX.X..X.XX....X...XXX.X.....................................XX.......X.XX..........XX.....................................XX....X.......X.X...X...XXX...X.....XX.XXXX..X........................X.....X.........X......

output:

101/1

result:

wrong answer 1st lines differ - expected: '89/1', found: '101/1'

Subtask #3:

score: 0
Wrong Answer

Test #49:

score: 1
Accepted
time: 0ms
memory: 5968kb

input:

7 10000
..XXXX.XXX.X......X..XX.XX......XX.XX.X...X...X..X.XX........XXXX..X..X..X.X.XX.XX..XX..X...XXX.X.X.XXXX..X....X.X.X.X.....X..XX.XXX.X.X...XXXXX.XXX..X.XX...XX...X...X.XX.X...X.XX..X....XXX...X....XX........XXXXX...X..X....XXX...XXXX.X.X.X..XXXX....XX...X.X.XXX....XXXX.XX.X.X.XX..X.XXXXXXXXX...

output:

-1

result:

ok single line: '-1'

Test #50:

score: 1
Accepted
time: 11ms
memory: 22848kb

input:

8 10000
XXX...X...XX.XX...X.X...XX..X...X.XX.X.X...X.X..X.XXXXX....X.X.X..XXXXXXXX...X..X..X.XXX.X.X...XXXXX..XX...X...X.X...X..X..X.XXX.X..X...XX....XX..X.X.X..XXXXX..X.XX...XX.....X.X.XXX...XXXXXX.XXXXXX.XX...XXX.X......XXX.XXXX........XXX..X.X..X......XXX...X..X...X.X.X...X...XX..XXXX..XX.X.X.X.....

output:

10/1

result:

ok single line: '10/1'

Test #51:

score: 1
Accepted
time: 7ms
memory: 18760kb

input:

8 10000
.........X.X.....XX.XX.........................X....................XXXXX..............................X...........X......X......X....................XX.....X.X.XXX...X.....X..X....................X.......................................X...X...X............X....................X.X.............

output:

649/1

result:

ok single line: '649/1'

Test #52:

score: 1
Accepted
time: 10ms
memory: 16964kb

input:

8 10000
...................XXXX.................X.........................X................XX...X....X..X......X...X.......XX..........X...XXXX..XX............X..XX......X....X.X.X..........X......X........X.....................X...........X...........................X..X..X..........XX..XXXX..........

output:

1297/2

result:

ok single line: '1297/2'

Test #53:

score: 0
Wrong Answer
time: 8ms
memory: 19012kb

input:

8 9997
.....................................................................................................................................................................................................................................................................................X..................

output:

432/1

result:

wrong answer 1st lines differ - expected: '401/1', found: '432/1'

Subtask #4:

score: 0
Wrong Answer

Test #64:

score: 0
Wrong Answer
time: 32ms
memory: 21036kb

input:

10 30000
......................................................................................................................................................................................................................................................................................................

output:

3000/1

result:

wrong answer 1st lines differ - expected: '15000/1', found: '3000/1'

Subtask #5:

score: 0
Wrong Answer

Test #79:

score: 0
Wrong Answer
time: 81ms
memory: 33488kb

input:

12 50000
.XXXXXXXXXXXX.XXXXXXX.XX.X.XX....XX....XXXXX.XXXX.XX.XXXXXXXXXXXXX..XXXXX.X.XXX.XX..XXXXXX..XXX.XXXXX.XXXXXX.X.X..XXXXXXXXXXX.XX.XX.X.X.XX.XXXXXXXXXX.XXXXXXXXXX..XXX.XX.XXXXX.XXXXXX.XX.XXXX.XXXXX.XXXX.XXXX.XXXXXX.X.XX.XXX.XX.XXXX..X.X.XXXXXXXXXXXX...XXXXX.XX.XX...X.X..XXX.X...XXX..XXXXXXX.....

output:

7/1

result:

wrong answer 1st lines differ - expected: '0/1', found: '7/1'

Subtask #6:

score: 0
Wrong Answer

Test #96:

score: 1
Accepted
time: 2ms
memory: 6516kb

input:

14 60000
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

-1

result:

ok single line: '-1'

Test #97:

score: 0
Wrong Answer
time: 103ms
memory: 36244kb

input:

14 59999
......................................................................................................................................................................................................................................................................................................

output:

59999/14

result:

wrong answer 1st lines differ - expected: '59999/2', found: '59999/14'

Subtask #7:

score: 0
Wrong Answer

Test #116:

score: 1
Accepted
time: 125ms
memory: 44780kb

input:

15 70000
XXXXXXXXXXXXXXXXXXX.XXXXXXXXXXXX.XX.XXXXXXXXXXXXX.XXXXXXXXXXXXX.XXXXXX.XXXXXXXXXXXXXXXXXX.X.XXXXXXXXXXX.X.XXXXXXXXXXXXXXXXXXXXXXXX.XXXXXXXXXXXXXXXXXXXXXX.XXXX.XXXXXXXXXXX.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.XXXXXXXXXXXXXXXXXXX.XXXXXXXXXXX.XXXXXXXXXXXX.XXXXX.XXXXXXXXXX.XXXXXXXXXXXXXXXX.XXXXX...

output:

0/1

result:

ok single line: '0/1'

Test #117:

score: 1
Accepted
time: 146ms
memory: 46000kb

input:

15 70000
.X.X..X....XXX..X.XX..XX.X....X.XX.XXX.X.X....XXX...XX.X..X.XXXX...XX..X.X..X...XX.XX.X..XXX....XX...XX.......XX.....X...XX...X.XX.X...X...XXXX.X....X.X....XXX.X...XXX..X.X..XX.X.XX.X..X.XXXX...XXXXX.XX.XX..X..XXX.X......XX...X.X.XXXX.XX..XX.XX..XX..XXX.X.XX....XXXX.X.X..XX..X.XX..X.X.XXXXX...

output:

13/1

result:

ok single line: '13/1'

Test #118:

score: 1
Accepted
time: 144ms
memory: 40660kb

input:

15 69999
...................X..X.X.......................X...X.XXXX.................................................................................................................................................X.................................................................X........................

output:

2293/1

result:

ok single line: '2293/1'

Test #119:

score: 0
Wrong Answer
time: 147ms
memory: 41520kb

input:

15 69999
.X....X.......................X.X.............................................................................................X.X.XXX.X............................................................................................X......X............................X.X..................X.........

output:

4625/2

result:

wrong answer 1st lines differ - expected: '4585/2', found: '4625/2'

Subtask #8:

score: 0
Wrong Answer

Test #135:

score: 1
Accepted
time: 3ms
memory: 6204kb

input:

16 80000
XX..XX..X.XXX.XX.XXX.XX...X..X..X....XX.....X........XXX.XXXX.X....X.XXXXX...X.....XX.X..XXX.X..X.XXX....XXXX...XX..X..X...X.XX..XXXX.XX.X....XX.X.XXX....XXX...X.XXXX..XXXXX..XX.XX..X.XXXXX.X..XXXX.XXXXX.X.XXX.X...XX.XXXXX..X..X....XX.....XX.X.XX..X.XXX.X..X..X....X.X..X..XX...X...XXX.X...X...

output:

-1

result:

ok single line: '-1'

Test #136:

score: 1
Accepted
time: 180ms
memory: 48804kb

input:

16 80000
XX..X..X..XX.XX..X.X.XXXX.X.....XX...XXXX..X.XXXXX.X....X.XXX...XX..X.X.X.XXXX.XXXXXXXXX.XXX.XXX..X.X.XXXX..XX.XXX....XXXX...X..X.XXX.XX.X.X.X.XX.XX.X.X......XX.X.XX..X....XXXX.X.X...X..X..X.X...X.XX..X.XX.X.XXXXXXXX.XX.X..X.....X.X.XX...XXX....XX..X.XXX.X..X.X..X..XXXX.XX.X.X.XX..XX.X..XXX...

output:

13/1

result:

ok single line: '13/1'

Test #137:

score: 1
Accepted
time: 170ms
memory: 45268kb

input:

16 80000
......................................................................................................................................................................................................................................................................................................

output:

2433/1

result:

ok single line: '2433/1'

Test #138:

score: 1
Accepted
time: 166ms
memory: 45608kb

input:

16 80000
......................................................................................................................................................................................................................................................................................................

output:

4865/2

result:

ok single line: '4865/2'

Test #139:

score: 1
Accepted
time: 143ms
memory: 40284kb

input:

16 65535
......................X....X....X.XXX................XX.........X.X.....................................X.....X............X...........................X.....X......X.X............X.....X....X....X..XX........X.X......................XX...X..XXXXX................................X....X..........

output:

1861/1

result:

ok single line: '1861/1'

Test #140:

score: 1
Accepted
time: 140ms
memory: 41632kb

input:

16 65535
.X..........................................................XXXXX.....XXXXX..........X......X...............................................................................................................XX...XX...............................................XXX.XX..............................

output:

3721/2

result:

ok single line: '3721/2'

Test #141:

score: 1
Accepted
time: 191ms
memory: 46788kb

input:

16 80000
......................................X..X.X..X............................................XX...X...............................X......................X................X...........X.X............................X.........................................................XXXX.....................

output:

3794/13

result:

ok single line: '3794/13'

Test #142:

score: 0
Wrong Answer
time: 167ms
memory: 44568kb

input:

16 80000
.............................................X.XX....X.XX.........................................................................................................................................................................................................X.............X...X.................

output:

58913/12

result:

wrong answer 1st lines differ - expected: '74012/3', found: '58913/12'

Subtask #9:

score: 0
Wrong Answer

Test #154:

score: 1
Accepted
time: 216ms
memory: 48852kb

input:

17 90000
XXX.XX.XXXX.X..X..XX.XXX..XX.X....X..X..XXXXX.XX....X.XX.X.XXXXX.X..X....X..XX..X.X.XX.XX..X.XX..XX...X.XXXXX.......X...XX......X..XX.......XX..X.X..X.X.X.XX..X..XXX.XXXXX..XX.XX.X....X.XXX.X.X.XXXXXX..XX.XX.X....X......X..XX...X.XXX.X..XXX.XX.X..XXX.XXXXX.X.XXXX.X.X..X.XXX....X.X..XXX.XX.....

output:

13/1

result:

ok single line: '13/1'

Test #155:

score: 1
Accepted
time: 206ms
memory: 50396kb

input:

17 90000
......................................................................................................................................................................................................................................................................................................

output:

2643/1

result:

ok single line: '2643/1'

Test #156:

score: 1
Accepted
time: 223ms
memory: 49124kb

input:

17 90000
......................................................................................................................................................................................................................................................................................................

output:

5285/2

result:

ok single line: '5285/2'

Test #157:

score: 0
Wrong Answer
time: 215ms
memory: 48712kb

input:

17 90000
.............................................XX.....XX.X......X..............................................XX.XX................X.XX.X..........................................................................X.............X...XXX.......XX.XXXXX...........................X................X...

output:

2554/1

result:

wrong answer 1st lines differ - expected: '2422/1', found: '2554/1'

Subtask #10:

score: 0
Wrong Answer

Test #172:

score: 0
Wrong Answer
time: 410ms
memory: 54008kb

input:

18 100000
.....................................................................................................................................................................................................................................................................................................

output:

50000/9

result:

wrong answer 1st lines differ - expected: '50000/1', found: '50000/9'