QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#952020#10243. Opieka [A]zlt0 1041ms174580kbC++142.0kb2025-03-26 18:55:392025-03-26 18:55:41

Judging History

This is the latest submission verdict.

  • [2025-03-26 18:55:41]
  • Judged
  • Verdict: 0
  • Time: 1041ms
  • Memory: 174580kb
  • [2025-03-26 18:55:39]
  • 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[maxn];
int a[19][maxn], b[maxn];

inline bool check(int x) {
	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 + 1);
		int k = 0;
		for (int j = 1; j <= m; ++j) {
			for (int _ = 0; _ < n; ++_) {
				s[i][++k] = t[j];
			}
		}
	}
	m *= n;
	for (int i = 1; i <= m; ++i) {
		bool fl = 1;
		for (int j = 0; j < n && fl; ++j) {
			fl &= (s[j][i] == 'X');
		}
		if (fl) {
			puts("-1");
			return;
		}
	}
	int l = 1, r = m, ans = 0;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) {
			ans = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	int p = ans, q = n;
	int g = __gcd(p, q);
	p /= g;
	q /= g;
	printf("%d/%d\n", p, q);
}

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: 14360kb

input:

1 1
.

output:

0/1

result:

ok single line: '0/1'

Test #2:

score: 0
Wrong Answer
time: 2ms
memory: 22252kb

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:

88/5

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #36:

score: 1
Accepted
time: 5ms
memory: 24408kb

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: 5ms
memory: 27248kb

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: 5ms
memory: 24332kb

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: 5ms
memory: 27252kb

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: 5ms
memory: 26920kb

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: 6ms
memory: 27248kb

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: 6ms
memory: 27120kb

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: 7ms
memory: 27084kb

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: 4ms
memory: 27004kb

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: 18248kb

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: 60ms
memory: 33396kb

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: 140ms
memory: 37112kb

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: 144ms
memory: 35180kb

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: 79ms
memory: 35224kb

input:

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

output:

401/1

result:

ok single line: '401/1'

Test #54:

score: 1
Accepted
time: 88ms
memory: 37100kb

input:

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

output:

400/1

result:

ok single line: '400/1'

Test #55:

score: 1
Accepted
time: 139ms
memory: 30676kb

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: 142ms
memory: 35120kb

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: 128ms
memory: 34792kb

input:

8 8192
........................................................................................................................................................................................................................................................................................................

output:

5955/8

result:

wrong answer 1st lines differ - expected: '6091/5', found: '5955/8'

Subtask #4:

score: 0
Wrong Answer

Test #64:

score: 0
Wrong Answer
time: 70ms
memory: 53120kb

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: 4ms
memory: 30416kb

input:

14 60000
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

-1

result:

ok single line: '-1'

Test #97:

score: 0
Wrong Answer
time: 280ms
memory: 98860kb

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: 382ms
memory: 118996kb

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: 6ms
memory: 36680kb

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
Wrong Answer

Test #172:

score: 0
Wrong Answer
time: 1041ms
memory: 174580kb

input:

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

output:

50000/9

result:

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