QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#952033 | #10243. Opieka [A] | zlt | 0 | 2953ms | 144784kb | C++14 | 2.2kb | 2025-03-26 19:01:30 | 2025-03-26 19:01:32 |
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 = 1800100;
int n, m, f[(1 << 18) + 50];
char s[19][maxn], t[19][maxn];
int a[19][maxn], b[maxn];
inline bool check(int x, int m) {
mems(f, 0x3f);
f[0] = 0;
mems(b, 0);
for (int i = 0; i < n; ++i) {
for (int j = 1; j <= m; ++j) {
a[i][j] = a[i][j - 1] + (s[i][j] == 'X');
if (s[i][j] == '.') {
++b[j];
}
}
}
for (int i = 1; i <= m; ++i) {
b[i] = b[i - 1] + (b[i] <= 1);
}
for (int S = 0; S < (1 << n); ++S) {
int v = f[S];
if (v > m) {
continue;
}
for (int i = 0; i < n; ++i) {
if (S & (1 << i)) {
continue;
}
for (int j = v; j + x <= m; ++j) {
if (b[j + x] == b[j] && a[i][j + x] == a[i][j]) {
f[S | (1 << i)] = min(f[S | (1 << i)], j + x);
break;
}
}
}
}
return f[(1 << n) - 1] <= m;
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) {
scanf("%s", t[i] + 1);
}
for (int i = 1; i <= m; ++i) {
bool fl = 1;
for (int j = 0; j < n && fl; ++j) {
fl &= (t[j][i] == 'X');
}
if (fl) {
puts("-1");
return;
}
}
ll ansx = 0, ansy = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < n; ++j) {
int tot = 0;
for (int k = 1; k <= m; ++k) {
for (int _ = 0; _ < i; ++_) {
s[j][++tot] = t[j][k];
}
}
}
ll l = 1, r = m * i, ans = 0;
while (l <= r) {
ll mid = (l + r) >> 1;
if (check(mid, m * i)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
if (ans * ansy > ansx * i) {
ansx = ans;
ansy = i;
}
}
ll g = __gcd(ansx, ansy);
printf("%lld/%lld\n", ansx / g, ansy / g);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 1
Accepted
time: 1ms
memory: 17804kb
input:
1 1 .
output:
0/1
result:
ok single line: '0/1'
Test #2:
score: 0
Wrong Answer
time: 10ms
memory: 32064kb
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: 25ms
memory: 35872kb
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: 24ms
memory: 36368kb
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: 25ms
memory: 36364kb
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: 1
Accepted
time: 26ms
memory: 35536kb
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:
89/1
result:
ok single line: '89/1'
Test #40:
score: 1
Accepted
time: 24ms
memory: 35668kb
input:
6 997 ............X.......................X..X.....X...........X..........................XX..X...X........................XX..X..X.XX..X.....XX............................XX...............................................XX..X.X.....XX......X.....XXX...............X........X................XXX..XX.....
output:
177/2
result:
ok single line: '177/2'
Test #41:
score: 1
Accepted
time: 25ms
memory: 36148kb
input:
6 1000 ....................XX...............................................XX.XXX....................XXXXX.....XX.................X.........................X......XXXX...XX....XX....................XX..X..........................................................................X.........X..............
output:
51/1
result:
ok single line: '51/1'
Test #42:
score: 1
Accepted
time: 24ms
memory: 36368kb
input:
6 1000 ............X............X..X............XX...X.X.XX....X......XXXXX..XXXX....XXX...XXXX....X...X..........X...............X................X..X...........................................................................X.X................X.X....X..X..........X..................X.................
output:
101/2
result:
ok single line: '101/2'
Test #43:
score: 1
Accepted
time: 26ms
memory: 34324kb
input:
6 1000 ............XXXXX..................XXX............X..............XXX.....XX.X...X...........XX........X.X.......XXX.....XXX.XXX.............................X........X..................X........X...X..X.X......XXXX.X......X.....X.........X.XX..X..XX.X....XX...XX...XX..............................
output:
745/6
result:
ok single line: '745/6'
Test #44:
score: 0
Wrong Answer
time: 23ms
memory: 36204kb
input:
6 1000 ..X....................XX.........XX........XX.X...X..XX....X...........X.X..XXXX....X...XX.X..............................X....................X.X........XX...X...XXX.........XX...X.........X.....................XX.......................X.........X.....XX...............X.................X.X....
output:
484/3
result:
wrong answer 1st lines differ - expected: '529/2', found: '484/3'
Subtask #3:
score: 0
Wrong Answer
Test #49:
score: 1
Accepted
time: 1ms
memory: 16208kb
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: 288ms
memory: 45808kb
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: 615ms
memory: 45984kb
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: 584ms
memory: 45928kb
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: 1
Accepted
time: 328ms
memory: 45880kb
input:
8 9997 .....................................................................................................................................................................................................................................................................................X..................
output:
401/1
result:
ok single line: '401/1'
Test #54:
score: 1
Accepted
time: 316ms
memory: 45556kb
input:
8 9997 ......................................................................................................................................................................................................X.................................................................................................
output:
400/1
result:
ok single line: '400/1'
Test #55:
score: 1
Accepted
time: 571ms
memory: 48408kb
input:
8 10000 ....................X............XX...........................................................XXXX.X.XXXXXXXXX...............X....X......XX........X.....XX..................X........................................X...............X.........................XX........X.......................X....
output:
657/1
result:
ok single line: '657/1'
Test #56:
score: 1
Accepted
time: 574ms
memory: 46324kb
input:
8 10000 ...................X.X..XXX....................................XX.X...............XXX...X.......................................X...........................X.XXX.............X..XXX..........X.....................................................................................XXXX........X......
output:
1313/2
result:
ok single line: '1313/2'
Test #57:
score: 0
Wrong Answer
time: 546ms
memory: 45396kb
input:
8 8192 ........................................................................................................................................................................................................................................................................................................
output:
3722/5
result:
wrong answer 1st lines differ - expected: '6091/5', found: '3722/5'
Subtask #4:
score: 0
Wrong Answer
Test #64:
score: 0
Wrong Answer
time: 332ms
memory: 72092kb
input:
10 30000 ......................................................................................................................................................................................................................................................................................................
output:
3000/1
result:
wrong answer 1st lines differ - expected: '15000/1', found: '3000/1'
Subtask #5:
score: 0
Time Limit Exceeded
Test #79:
score: 0
Time Limit Exceeded
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:
result:
Subtask #6:
score: 0
Wrong Answer
Test #96:
score: 1
Accepted
time: 0ms
memory: 28488kb
input:
14 60000 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
-1
result:
ok single line: '-1'
Test #97:
score: 0
Wrong Answer
time: 2089ms
memory: 125444kb
input:
14 59999 ......................................................................................................................................................................................................................................................................................................
output:
59999/14
result:
wrong answer 1st lines differ - expected: '59999/2', found: '59999/14'
Subtask #7:
score: 0
Time Limit Exceeded
Test #116:
score: 1
Accepted
time: 2953ms
memory: 144784kb
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: 0
Time Limit Exceeded
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:
result:
Subtask #8:
score: 0
Time Limit Exceeded
Test #135:
score: 1
Accepted
time: 1ms
memory: 32592kb
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: 0
Time Limit Exceeded
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:
result:
Subtask #9:
score: 0
Time Limit Exceeded
Test #154:
score: 0
Time Limit Exceeded
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:
result:
Subtask #10:
score: 0
Time Limit Exceeded
Test #172:
score: 0
Time Limit Exceeded
input:
18 100000 .....................................................................................................................................................................................................................................................................................................