QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#952033#10243. Opieka [A]zlt0 2953ms144784kbC++142.2kb2025-03-26 19:01:302025-03-26 19:01:32

Judging History

This is the latest submission verdict.

  • [2025-03-26 19:01:32]
  • Judged
  • Verdict: 0
  • Time: 2953ms
  • Memory: 144784kb
  • [2025-03-26 19:01:30]
  • 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 = 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
.....................................................................................................................................................................................................................................................................................................

output:


result: