QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#952209 | #10243. Opieka [A] | zlt | 0 | 410ms | 54008kb | C++14 | 3.4kb | 2025-03-26 21:06:11 | 2025-03-26 21:06:18 |
Judging History
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'