QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#581234#4632. Card Sharkchuchu#AC ✓12ms12688kbC++142.1kb2024-09-22 11:01:252024-09-22 11:01:26

Judging History

你现在查看的是最新测评结果

  • [2024-09-22 11:01:26]
  • 评测
  • 测评结果:AC
  • 用时:12ms
  • 内存:12688kb
  • [2024-09-22 11:01:25]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define FINISH cerr << "FINISH" << endl;
#define debug(x) cerr << #x << " == " << x << endl
#define el '\n'
#define fir first
#define sec second
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1000000007;
const int inf = 0x3f3f3f3f;
const int N = 200020;
void solve()
{
	int n, m, d, mn = inf;
	cin >> n >> m >> d;
	vector<vector<PII>> edge(m + 1);
	vector<int> inp(m + 1, 0);
	for (int j = 1; j <= n; j++) {
		string s;
		cin >> s;
		int st = 0;
		for (int i = 0; i < s.size(); i++) {
			if (s[i] == '1') {
				st = i;
				break;
			}
		}
		if (st + 1 == d) {
			mn = min(mn, j);
		}
		int cnt = 0;
		for (int i = st + 1; i < s.size(); i++) {
			if (i % m == st && s[i] == '0') {
				cout << "-1" << el;
				return;
			}
			if (i % m != st && s[i] == '1') {
				cout << "-1" << el;
				return;
			}
			if (s[i] == '0') {
				cnt++;
			}
			else {
				cnt = 0;
			}
		}
		if (st >= m || cnt >= m) {
			cout << "-1" << el;
			return;
		}
		edge[st].push_back(PII(m - 1 - cnt, j));
		inp[m - 1 - cnt]++;
		inp[st]--;
		// cout << "addedge " << st << " " << m - 1 - cnt << " " << i << endl;
	}
	/*for (int i = 0; i <= m; i++) {
		if (inp[i] != 0) {
			cout << "-1" << el;
			return;
		}
	}*/
	for (int i = 0; i <= m; i++) {
		sort(edge[i].begin(), edge[i].end(),
			 [&](PII x, PII y) { return x.sec < y.sec; });
	}
	if (mn == -1) {
		cout << "-1" << el;
		return;
	}
	// FINISH
	int st = d - 1;
	vector<int> b(m + 1, 0);
	vector<int> ans;
	function<void(int, int)> dfs = [&](int x, int las) {
		// cout << x << endl;
		for (int i = b[x]; i < edge[x].size(); i = b[x]) {
			// cout << "!" << endl;
			b[x] = i + 1;
			dfs(edge[x][i].fir, edge[x][i].sec);
		}
		ans.push_back(las);
	};
	dfs(st, 0);
	// cout << ans.size() << el;
	if (ans.size() != n + 1) {
		cout << "-1" << el;
		return;
	}
	for (int i = ans.size() - 2; i >= 0; i--) {
		cout << ans[i] << " ";
	}
	cout << el;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	// cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3784kb

input:

5 4 3
0100010
00100
001000100
0010
0100010

output:

2 1 3 5 4 

result:

ok single line: '2 1 3 5 4 '

Test #2:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

4 2 1
010
10101
010
10101

output:

2 1 4 3 

result:

ok single line: '2 1 4 3 '

Test #3:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

1 5 3
001000010000100

output:

1 

result:

ok single line: '1 '

Test #4:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

2 5 3
01000
00010

output:

-1

result:

ok single line: '-1'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

1 5 3
11111

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

10 5 3
000010000100
0001000010000100001
000100
00010
00010000100
0010
00001000010000100001000010
00010
001
001000010

output:

6 2 1 9 7 3 10 4 8 5 

result:

ok single line: '6 2 1 9 7 3 10 4 8 5 '

Test #7:

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

input:

1000 5 4
010000100
00100
001000
00010000100001000
0010000100
100
00001000010000
000010
00010000100001000010
01000010000100
100
0000100
1
00010000
0010
0001
10000100
00001000
1
000100
0000100001
000010000100001000
00100001
010
00100001000010000100
0000100001
010
00100001000010000100001
0000100001
001...

output:

4 1 2 3 10 5 15 9 14 6 23 7 11 25 28 8 16 12 30 31 13 18 24 20 39 27 34 36 37 21 22 35 47 52 26 29 40 43 44 53 38 17 56 19 42 58 59 60 32 33 57 48 45 65 50 54 71 63 74 41 64 51 73 79 75 80 81 90 62 68 46 70 67 99 87 100 69 108 72 97 76 77 82 83 86 88 49 93 94 98 103 55 101 61 102 106 104 109 105 112...

result:

ok single line: '4 1 2 3 10 5 15 9 14 6 23 7 11...88 984 989 992 994 991 999 998 '

Test #8:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

1000 5 2
0001000010000100001
00100001
000010
0010000
000100001000
100001000010000100001000010000
010000100001
00010
1000010000100001000
010
010000100001000010
001000
1000010000
000010000100001000
10000
10000100
01000
100001000010
00100
00100
000010000
1000010000100001000010000100001
100
100001000010...

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 3ms
memory: 12688kb

input:

100000 5 2
1000010000
1000010
0010000100001
00100
01000010000100001
00010000
10000100
010000
001
010
1000010000
000010000
0000100001000
00100001000
010
1000
10000100
0100
1000
00001000010
01000010000
1
01
001000010000
0000100001
00100001000010
00010000100001
010
0010000100001000010
0010000100
00001
...

output:

5 12 1 2 6 7 3 13 8 11 16 10 27 20 38 25 31 32 4 9 33 15 50 14 18 24 17 26 56 61 21 19 23 34 22 39 29 69 28 79 30 35 108 37 51 55 57 70 41 111 36 72 47 113 73 42 76 78 40 120 46 48 43 49 52 124 80 81 44 128 83 62 53 64 45 135 66 58 85 137 59 54 60 74 77 140 63 86 67 84 96 98 65 88 99 68 101 90 71 10...

result:

ok single line: '5 12 1 2 6 7 3 13 8 11 16 10 2... 99986 99995 99999 99989 99994 '

Test #10:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

5 10 4
000010000000001000000
0100000
00000100000000
0001000000000100000000010000000001
000000000100000000010000

output:

4 5 3 2 1 

result:

ok single line: '4 5 3 2 1 '

Test #11:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

5 1000 581
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

4 5 2 1 3 

result:

ok single line: '4 5 2 1 3 '

Test #12:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

5 1000 406
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

-1

result:

ok single line: '-1'

Test #13:

score: 0
Accepted
time: 4ms
memory: 6924kb

input:

5 100000 91799
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

3 4 1 5 2 

result:

ok single line: '3 4 1 5 2 '

Test #14:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

10 20 17
000000000010000000000000000000100000000000000000001000000000000000000010000000000000000000100000000000000000001000000000000000000010000000000000000000100000000000000000001000000000000
0000000000001000
00000000000000001000000000000000000
000000000001000
100000000
0100000000000000000001000000...

output:

3 6 8 1 10 2 9 5 7 4 

result:

ok single line: '3 6 8 1 10 2 9 5 7 4 '

Test #15:

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

input:

100 200 114
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000010000...

output:

6 10 5 25 33 97 8 100 26 54 38 71 2 72 29 11 53 21 75 42 61 27 31 64 94 68 52 55 79 13 30 22 49 77 63 15 99 60 4 80 7 95 56 39 36 41 1 73 37 19 66 12 35 14 51 40 47 67 50 85 82 83 88 43 16 9 34 96 18 81 90 93 23 24 57 28 89 91 76 48 70 45 86 3 74 62 20 44 59 78 69 84 46 92 32 17 98 87 65 58 

result:

ok single line: '6 10 5 25 33 97 8 100 26 54 38... 69 84 46 92 32 17 98 87 65 58 '

Test #16:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

100 200 180
000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000...

output:

-1

result:

ok single line: '-1'

Test #17:

score: 0
Accepted
time: 3ms
memory: 3760kb

input:

1000 300 218
00000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

253 63 468 10 102 4 7 419 276 14 74 268 54 40 25 540 513 46 267 332 479 483 547 421 158 246 11 201 343 283 17 310 87 56 216 462 68 349 64 338 12 348 167 171 195 127 48 263 917 178 164 181 71 204 320 551 938 194 548 104 315 527 78 232 451 19 520 218 264 394 139 62 190 186 149 165 124 588 711 53 119 2...

result:

ok single line: '253 63 468 10 102 4 7 419 276 ...58 845 978 913 955 986 665 901 '

Test #18:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

100 5 2
0001000
01
000010000
00010000
10
00010
0100
00100
00010000
10000
00010
00001
0010
01000
100
10
000100
0100
010000
00010
00001000
01
100
00010
1000
0100
00010000
00001000
00001000
01000
0010000
01
01000
0010
010
001000
1
001000
00010
010000
001000
001000
10
010000
00100
0010000
010000
00010
0...

output:

2 3 5 1 7 8 13 4 10 15 31 16 6 9 23 34 11 17 36 14 18 38 19 25 22 12 21 26 41 30 32 28 33 35 20 24 27 37 29 40 43 39 48 49 50 54 42 44 52 47 55 45 46 59 56 61 62 51 53 63 72 57 58 66 64 69 79 60 89 70 71 65 75 76 77 78 82 67 91 83 87 68 81 73 74 88 95 92 84 86 80 94 90 93 99 85 96 97 98 100 

result:

ok single line: '2 3 5 1 7 8 13 4 10 15 31 16 6...80 94 90 93 99 85 96 97 98 100 '

Test #19:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

100 5 2
00100
1
10000
000100
000100
00100
00010
00010
000100
0010
00100
000100
00001000
000100
00010
000100
01
00100
00010
00010
00100
000100
010000
00100
01000
00010
00010
00100
1000
000100
000100
00010
000100
000100
00010
000100
0010
00100
00010
0010
00100
00010
0010
00100
00010
0010
000100
000100...

output:

-1

result:

ok single line: '-1'

Test #20:

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

input:

1000 5 1
010
000100
0100
0010000
01000
01000
00010
0010
1000
00001
1000
000010000
1
001
0100
0001
01000
00001000
010
00100
001000
00100
1
00001
0010
00100
000010000
10000
0000100
100
0000100
00010000
00010
00001000
010
0010000
00100
00010
0001000
1
00001000
01
0001000
0010000
000010000
00001
010
000...

output:

9 1 2 4 11 3 8 7 16 10 12 13 18 5 6 15 14 24 27 23 29 20 21 17 19 32 28 30 22 25 33 38 39 35 43 42 31 26 36 40 34 47 48 37 44 50 58 61 41 57 76 60 49 82 83 52 45 54 46 51 84 85 86 63 69 53 65 55 73 88 72 77 79 89 87 92 59 62 95 80 56 99 98 102 101 104 70 64 106 91 93 100 103 71 113 108 114 74 66 75 ...

result:

ok single line: '9 1 2 4 11 3 8 7 16 10 12 13 1...9 984 993 995 996 1000 991 998 '

Test #21:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

1000 5 4
000010
10
000010
100
10
0010
10
00010
00001
00001
100
0001
00010000
0010
0001
0000100
100
00001
000100
0010000
0010000
0010
0000100
000010000
001
10
100
000100
000100
0010000
0001
000010000
000010
0001
00100
000010000
000010000
000010
100
0001
00001
100
10000
00010
10000
0010000
0010
10000
...

output:

-1

result:

ok single line: '-1'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

1000 5 5
010
1
10000
000010
100
100
0100
0000100
000100
0001
0010000
0001000
10
00001
00010000
1
1000
000010
001
01000
0010
1000
00100
001
1
0010
00001
001000
01000
00100
01000
1000
100
01
0010
000010
1000
0010
001
0000100
10
0100
00100
000010000
1
001000
00010
00100
00010
0001000
00010000
001
100
0...

output:

-1

result:

ok single line: '-1'

Test #23:

score: 0
Accepted
time: 12ms
memory: 12516kb

input:

100000 5 2
00010
10
000010
00001
00100
00010000
00001
1000
001
00100
0010000
10
00100
010000
01000
000010
0010000
000100
01000
0010
0010
000010000
100
001000
0010000
010
000010
00100
00010
00010000
100
1000
001
000100
010000
0001000
0001
010000
1
010000
001
001000
1
000100
0100
00010000
0000100
0001...

output:

14 2 1 6 8 15 19 26 18 5 9 3 29 30 12 34 10 11 23 13 17 31 20 36 35 32 38 39 4 7 16 37 22 43 27 44 21 46 51 47 24 40 55 45 25 56 28 33 49 41 59 60 67 50 61 53 76 42 62 48 52 64 63 69 84 68 66 71 77 91 93 78 81 96 100 70 86 82 85 54 57 94 95 106 58 107 113 98 102 65 87 79 72 117 97 123 101 124 115 92...

result:

ok single line: '14 2 1 6 8 15 19 26 18 5 9 3 2... 99979 99997 99999 99998 99982 '

Test #24:

score: 0
Accepted
time: 10ms
memory: 10836kb

input:

100000 5 5
00100
00001
00100
00100
00100
00001
00100
0000100
00010000
00001
1000
001
001
0000100
00001
001
0000100
00001
0000100
010
00001
001
001
0000100
00100
0000100
00001
0000100
0000100
00010000
001
0000100
00001
10
0000100
0000100
010000
001
01000
001
00100
0000100
001
001
01000
00001
00100
00...

output:

-1

result:

ok single line: '-1'

Test #25:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

5 100 57
0000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000100000000000000000000000000000000...

output:

1 2 3 4 5 

result:

ok single line: '1 2 3 4 5 '

Test #26:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

5 100 85
0000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000...

output:

-1

result:

ok single line: '-1'

Test #27:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

5 1000 669
0000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2 5 3 4 1 

result:

ok single line: '2 5 3 4 1 '

Test #28:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

5 1000 517
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

-1

result:

ok single line: '-1'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

5 1000 328
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

-1

result:

ok single line: '-1'

Test #30:

score: 0
Accepted
time: 0ms
memory: 6404kb

input:

5 100000 81183
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2 3 1 4 5 

result:

ok single line: '2 3 1 4 5 '

Test #31:

score: 0
Accepted
time: 11ms
memory: 12496kb

input:

100000 5 2
00001000
1
00001000
1
1
1
1
00001000
00001000
00001000
1
00001000
1
00001000
010000
1
00001000
00001000
010000
010000
1
00001000
1
00001000
010000
1
00001000
1
00001000
00001000
1
1
1
010000
00001000
00001000
00001000
00001000
00001000
010000
1
00001000
00001000
010000
010000
010000
01000...

output:

15 2 1 19 4 3 20 5 8 25 6 9 34 7 10 40 11 12 44 13 14 45 16 17 46 21 18 47 23 22 48 26 24 51 28 27 52 31 29 53 32 30 54 33 35 57 41 36 65 56 37 67 58 38 68 60 39 70 63 42 76 64 43 78 66 49 79 69 50 85 71 55 93 75 59 96 77 61 98 80 62 100 81 72 102 86 73 104 88 74 105 94 82 112 99 83 114 103 84 116 1...

result:

ok single line: '15 2 1 19 4 3 20 5 8 25 6 9 34...99995 99992 100000 99999 99998 '

Test #32:

score: 0
Accepted
time: 2ms
memory: 3688kb

input:

100000 5 5
001
001
001
000010
000010
001
000100
001
000010
001
001
000100
000010
000100
001
000010
001
000010
001
000100
000100
001
000100
001
000010
000010
001
001
000100
000010
001
001
000100
001
001
001
000100
000010
000100
000100
001
000100
000010
000100
000010
001
000010
000010
000100
000100
00...

output:

-1

result:

ok single line: '-1'

Test #33:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

7 2 2
1010
010
0001
1
10
01
01

output:

-1

result:

ok single line: '-1'