oj.uz

Submission #793740

# Submission time Handle Problem Language Result Execution time Memory
793740 2023-07-26T06:08:04 Z GEN 이지후(#10094) Flip it and Stick it (CCO23_day2problem1) C++17
25 / 25
 5 ms 1620 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()

int solve(string s) {
	if (sz(s) <= 2)
		return 0;
	int cnt = count(all(s), '1');
	if (3 * cnt + 2 >= sz(s)) {
		int ans = 0;
		int fast = 0;
		int canfast = 0;
		if (s[0] == '1')
			canfast++;
		if (s.back() == '1')
			canfast++;
		for (int i = 0; i < sz(s) - 1; i++) {
			if (s.substr(i, 2) == "11")
				canfast++;
		}
		for (int i = 0; i < sz(s);) {
			if (s[i] == '1') {
				i++;
				continue;
			}
			int j = i;
			while (j < sz(s) && s[i] == s[j])
				j++;
			int d = j - i;
			if (d >= 2) {
				if (d % 2 == 1)
					ans++, d--;
				fast += d / 2 - 1;
			}
			i = j;
		}
		if (fast <= canfast) {
			ans += fast;
		} else {
			ans += canfast;
			ans += fast * 2 - canfast * 2;
		}
		return ans;
	} else {
		return -1;
	}
}

int dm(string s) {
	map<string, int> vis;
	queue<pair<string, int>> que;
	auto enq = [&](string s, int d) {
		if (!vis.count(s)) {
			vis[s] = d;
			que.emplace(s, d);
		}
	};
	enq(s, 0);
	while (sz(que)) {
		auto [s, d] = que.front();
		bool ok = 0;
		for (int i = 0; i + 3 <= sz(s); i++) {
			if (s.substr(i, 3) == "000") {
				ok = 1;
				break;
			}
		}
		if (!ok)
			return d;
		que.pop();
		for (int i = 0; i < sz(s); i++) {
			for (int j = 2; j <= sz(s) - i; j++) {
				auto k = s;
				reverse(k.begin() + i, k.begin() + i + j);
				enq(k, d + 1);
			}
		}
	}
	return -1;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string s, t;
	cin >> s >> t;
	if (sz(t) == 1) {
		if (count(all(s), t[0]) == 0)
			cout << "0\n";
		else
			cout << "-1\n";
		return 0;
	}
	if (sz(t) == 2) {
		if (t[0] != t[1]) {
			if (t[0] == '0') {
				for (auto &x : s)
					x ^= 1;
			}
			t = "10";
			vector<int> poses;
			for (int i = 0; i < sz(s); i++) {
				if (s[i] == '1')
					poses.push_back(i);
			}
			poses.push_back(sz(s));
			int ans = 0;
			for (int i = 1; i < sz(poses); i++)
				if (poses[i - 1] + 1 != poses[i])
					ans++;
			cout << ans << "\n";
		} else {
			int cnt = count(all(s), t[0]);
			if (2 * cnt - 1 <= sz(s)) {
				int ans = 0;
				for (int i = 0; i + 1 < sz(s); i++) {
					if (s[i] == t[0] && s[i + 1] == t[0])
						ans++;
				}
				cout << ans << "\n";
			} else {
				cout << "-1\n";
			}
		}
		return 0;
	}
	if (t[0] == '1') {
		for (auto &x : s)
			x ^= 1;
		for (auto &x : t)
			x ^= 1;
	}
	if (t[2] == '1') {
		int ans = 0;
		for (int i = 0; i + 3 <= sz(s); i++) {
			if (s.substr(i, 3) == t)
				ans++;
		}
		cout << ans << "\n";
		return 0;
	}
	if (t[1] == '1') {
		int ans = 0;
		for (int i = 0; i + 3 <= sz(s); i++) {
			if (s.substr(i, 3) == t) {
				ans++;
			}
		}
		cout << (ans + 1) / 2 << "\n";
		return 0;
	}
	cout << solve(s) << "\n";
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 2 ms 1620 KB Output is correct
8 Correct 2 ms 1112 KB Output is correct
9 Correct 2 ms 1112 KB Output is correct
10 Correct 2 ms 1112 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 2 ms 1620 KB Output is correct
8 Correct 2 ms 1112 KB Output is correct
9 Correct 2 ms 1112 KB Output is correct
10 Correct 2 ms 1112 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 2 ms 1620 KB Output is correct
21 Correct 2 ms 1620 KB Output is correct
22 Correct 2 ms 1112 KB Output is correct
23 Correct 2 ms 1112 KB Output is correct
24 Correct 3 ms 1112 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 2 ms 604 KB Output is correct
28 Correct 2 ms 604 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 2 ms 604 KB Output is correct
32 Correct 2 ms 604 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 224 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 3 ms 604 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 3 ms 604 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 3 ms 604 KB Output is correct
19 Correct 3 ms 604 KB Output is correct
20 Correct 3 ms 604 KB Output is correct
21 Correct 3 ms 604 KB Output is correct
22 Correct 3 ms 604 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 0 ms 224 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 3 ms 604 KB Output is correct
24 Correct 3 ms 604 KB Output is correct
25 Correct 3 ms 604 KB Output is correct
26 Correct 3 ms 604 KB Output is correct
27 Correct 3 ms 604 KB Output is correct
28 Correct 3 ms 604 KB Output is correct
29 Correct 3 ms 604 KB Output is correct
30 Correct 3 ms 604 KB Output is correct
31 Correct 3 ms 604 KB Output is correct
32 Correct 3 ms 604 KB Output is correct
33 Correct 3 ms 604 KB Output is correct
34 Correct 3 ms 604 KB Output is correct
35 Correct 3 ms 604 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 4 ms 732 KB Output is correct
39 Correct 5 ms 732 KB Output is correct
40 Correct 1 ms 732 KB Output is correct
41 Correct 5 ms 732 KB Output is correct
42 Correct 4 ms 732 KB Output is correct
43 Correct 4 ms 732 KB Output is correct
44 Correct 5 ms 732 KB Output is correct
45 Correct 1 ms 732 KB Output is correct
46 Correct 5 ms 732 KB Output is correct
47 Correct 4 ms 732 KB Output is correct
48 Correct 5 ms 736 KB Output is correct
49 Correct 0 ms 216 KB Output is correct
50 Correct 0 ms 224 KB Output is correct
51 Correct 0 ms 224 KB Output is correct
52 Correct 0 ms 212 KB Output is correct
53 Correct 0 ms 220 KB Output is correct
54 Correct 3 ms 612 KB Output is correct
55 Correct 4 ms 604 KB Output is correct
56 Correct 4 ms 608 KB Output is correct
57 Correct 4 ms 676 KB Output is correct
58 Correct 4 ms 608 KB Output is correct
59 Correct 3 ms 604 KB Output is correct
60 Correct 3 ms 604 KB Output is correct
61 Correct 0 ms 212 KB Output is correct
62 Correct 1 ms 216 KB Output is correct
63 Correct 0 ms 212 KB Output is correct
64 Correct 0 ms 212 KB Output is correct
65 Correct 3 ms 604 KB Output is correct
66 Correct 4 ms 604 KB Output is correct
67 Correct 4 ms 604 KB Output is correct
68 Correct 4 ms 604 KB Output is correct
69 Correct 4 ms 604 KB Output is correct
70 Correct 3 ms 604 KB Output is correct
71 Correct 4 ms 604 KB Output is correct
72 Correct 0 ms 212 KB Output is correct
73 Correct 0 ms 212 KB Output is correct