QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#297969#4632. Card Sharkdefyers#AC ✓20ms14380kbC++172.7kb2024-01-05 15:07:222024-01-05 15:07:23

Judging History

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

  • [2024-01-05 15:07:23]
  • 评测
  • 测评结果:AC
  • 用时:20ms
  • 内存:14380kb
  • [2024-01-05 15:07:22]
  • 提交

answer

#include "bits/stdc++.h"

#pragma GCC optimize("Ofast")
#pragma GCC targetr("avx2")

using namespace std;

using ll = long long;
using pii = pair<int, int>;

using vi = vector<int>;

#define sz(x) (int)(x.size())

vi eulerWalk(vector<vector<pii>> &gr, int nedges, int src = 0) {
	int n = sz(gr);
	vi D(n), its(n), eu(nedges), ret, s = {src};
	D[src]++;
	while (!s.empty()) {
		int x = s.back(), y, e, &it = its[x], end = sz(gr[x]);
		if (it == end) {
			ret.push_back(x); s.pop_back(); continue;
		}
		tie(y, e) = gr[x][it++];
		if (!eu[e]) {
			D[x]--, D[y]++;
			eu[e] = 1; s.push_back(y);
		}
	}
	for (int x : D) if (x < 0 || sz(ret) != nedges+1) return {};
	return {ret.rbegin(), ret.rend()};
}


void solve(int TC) {
	int n, m, b;
	cin >> n >> m >> b;

	int sum = 0;

	bool fail = false;
	vector<pii> a(n);
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		int sz = s.size();
		sum += sz;
		int prev = -1;
		int mn = -1;
		int mx = -1;
		for (int j = 0; j < sz; j++) {
			if (s[j] == '1') {
				if (prev == -1) {
					prev = j;
					mn = j;
					mx = j;
				}
				else {
					int diff = j - prev;
					if (diff != m) fail = true;
					mx = j;
					prev = j;
				}
			}
			else {
				continue;
			}
		}

		int pre = mn;
		int last = sz - mx - 1;

		if (prev != -1) {
			if (pre > m - 1 || last > m - 1) {
				fail = true;
				break;
			}
			a[i] = {pre, last};
		}
		else {
			if (sz > (m - 1)) {
				fail = true;
				break;
			}
			else {
				a[i] = {sz, sz};
			}
		}
	}

	int ed = (sum - 1) % m - (b - 1);
	ed = (ed % m + m) % m;

	// cout << ed << endl;


	if (fail) {
		cout << -1 << "\n";
		return;
	}

	// for (int i = 0; i < n; i++) {
	// 	cout << a[i].first << " " << a[i].second << endl;
	// }

	int E = 0;

	vector<vector<pii>> g(n + 1 + m);
	for (int i = 0; i < n; i++) {
		g[(n + 1) + a[i].first].push_back({i + 1, E++});
		g[i + 1].push_back({(n + 1) + (m - 1 - a[i].second), E++});
	}

	// g[(n + 1) + ed].push_back({(n + 1) + (b - 1), E++});

	// for (int i = 0; i < n + 1 + m; i++) {
	// 	for (auto [v, w]: g[i]) {
	// 		cout << i << " -> " << v << " ecnt: " << w << endl;
	// 	}
	// }

	auto res = eulerWalk(g, E, (n + 1) + b - 1);
	// for (auto x: res) {
	// 	cout << x << " ";
	// }
	// cout << "\n";
	if (res.size() == 0) {
		cout << "-1\n";
		return;
	}

	vector<int> ans;
	for (auto x: res) {
		if (x >= 1 && x <= n) {
			ans.push_back(x);
		}
	}

	for (int i = 0; i < n; i++) {
		cout << ans[i] << " \n"[i == n - 1];
	}
	
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cout << fixed << setprecision(10);

	int t = 1;
	// cin >> t;
	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3560kb

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

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

input:

1 5 3
001000010000100

output:

1

result:

ok single line: '1'

Test #4:

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

input:

2 5 3
01000
00010

output:

-1

result:

ok single line: '-1'

Test #5:

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

input:

1 5 3
11111

output:

-1

result:

ok single line: '-1'

Test #6:

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

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

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...988 984 989 992 994 991 999 998'

Test #8:

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

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

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...7 99986 99995 99999 99989 99994'

Test #10:

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

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

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

input:

5 1000 406
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

-1

result:

ok single line: '-1'

Test #13:

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

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

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

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...8 69 84 46 92 32 17 98 87 65 58'

Test #16:

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

input:

100 200 180
000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000...

output:

-1

result:

ok single line: '-1'

Test #17:

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

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 ...858 845 978 913 955 986 665 901'

Test #18:

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

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

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

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...89 984 993 995 996 1000 991 998'

Test #21:

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

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

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

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...8 99979 99997 99999 99998 99982'

Test #24:

score: 0
Accepted
time: 16ms
memory: 13756kb

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

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

input:

5 100 85
0000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000...

output:

-1

result:

ok single line: '-1'

Test #27:

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

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

input:

5 1000 517
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

-1

result:

ok single line: '-1'

Test #29:

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

input:

5 1000 328
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

-1

result:

ok single line: '-1'

Test #30:

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

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

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

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

input:

7 2 2
1010
010
0001
1
10
01
01

output:

-1

result:

ok single line: '-1'