oj.uz

Submission #969508

# Submission time Handle Problem Language Result Execution time Memory
969508 2024-04-25T08:55:02 Z SorahISA Flip it and Stick it (CCO23_day2problem1) C++17
25 / 25
 4 ms 1272 KB 
#ifndef SorahISA
#define SorahISA
#include SorahISA __FILE__ SorahISA

int Count(const string &S, const string &T) {
    if (SZ(T) == 1) return count(ALL(S), T[0]);
    int cnt = 0;
    for (int i = 0; i <= SZ(S)-SZ(T); ++i) {
        if (S.substr(i, SZ(T)) == T) ++cnt;
    }
    return cnt;
}

int solve0(string S) {
    if (Count(S, "0")) return -1;
    return 0;
}

int solve00(string S) {
    if (Count(S, "0") > Count(S, "1") + 1) return -1;
    return Count(S, "00");
}

int solve01(string S) {
    return (S.front() == '0') + (S.back() == '1') + Count(S, "10") - 1;
}

int solve000(string S) {
    if (Count(S, "0") > Count(S, "1") * 2 + 2) return -1;
    int ans = 0, n_adj = 0, n_single = 0, n_even = 0;
    S += "1";
    for (int i = 0, lst = -1; i < SZ(S); ++i) {
        if (S[i] == '1') {
            ans += (i - lst - 2) / 2;
                 if (i - lst - 1 == 0) ++n_adj;
            else if (i - lst - 1 == 1) ++n_single;
            else                       n_even += (i - lst - 1) / 2 - 1;
            lst = i;
        }
    }
    return ans + min(max(n_even - n_adj, int(0)), n_single);
}

int solve001(string S) {
    return Count(S, "001");
}

int solve010(string S) {
    return (Count(S, "010") + 1) / 2;
}

void solve() {
    string S; cin >> S;
    string T; cin >> T;
    
    auto flip = [&]() { for (char &c : S) c ^= 1; };
    auto rev  = [&]() { reverse(ALL(S)); };
    
    int ans = 0;
    if (T ==   "0")                ans = solve0(S);
    if (T ==   "1") flip(),        ans = solve0(S);
    if (T ==  "00")                ans = solve00(S);
    if (T ==  "01")                ans = solve01(S);
    if (T ==  "10")         rev(), ans = solve01(S);
    if (T ==  "11") flip(),        ans = solve00(S);
    if (T == "000")                ans = solve000(S);
    if (T == "001")                ans = solve001(S);
    if (T == "010")                ans = solve010(S);
    if (T == "011") flip(), rev(), ans = solve001(S);
    if (T == "100")         rev(), ans = solve001(S);
    if (T == "101") flip(),        ans = solve010(S);
    if (T == "110") flip(),        ans = solve001(S);
    if (T == "111") flip(),        ans = solve000(S);
    cout << ans << "\n";
}

int32_t main() {
    fastIO();
    
    int t = 1; // cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    
    return 0;
}

#else

#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
#define int i64
using f80 = long double;
#define double f80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

#ifdef local
#define fastIO() void()
#define debug(...) \
    fprintf(stderr, "\u001b[33m"), \
    fprintf(stderr, "At [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), \
    fprintf(stderr, "\u001b[0m")
template <typename T> void _do(T &&_t) { cerr << _t << "\n"; }
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) { cerr << _t << ", ", _do(_u...); }
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif

template <typename T, typename U> bool chmin(T &lhs, U rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }
template <typename T, typename U> bool chmax(T &lhs, U rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; }

#endif

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 996 KB Output is correct
4 Correct 1 ms 984 KB Output is correct
5 Correct 1 ms 996 KB Output is correct
6 Correct 1 ms 996 KB Output is correct
7 Correct 1 ms 1248 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 452 KB Output is correct
6 Correct 3 ms 992 KB Output is correct
7 Correct 2 ms 996 KB Output is correct
8 Correct 3 ms 996 KB Output is correct
9 Correct 3 ms 996 KB Output is correct
10 Correct 3 ms 996 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 452 KB Output is correct
6 Correct 3 ms 992 KB Output is correct
7 Correct 2 ms 996 KB Output is correct
8 Correct 3 ms 996 KB Output is correct
9 Correct 3 ms 996 KB Output is correct
10 Correct 3 ms 996 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 356 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 2 ms 996 KB Output is correct
21 Correct 4 ms 996 KB Output is correct
22 Correct 4 ms 996 KB Output is correct
23 Correct 3 ms 1016 KB Output is correct
24 Correct 3 ms 1204 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 3 ms 1036 KB Output is correct
27 Correct 3 ms 996 KB Output is correct
28 Correct 1 ms 996 KB Output is correct
29 Correct 3 ms 996 KB Output is correct
30 Correct 3 ms 996 KB Output is correct
31 Correct 4 ms 996 KB Output is correct
32 Correct 3 ms 1252 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 2 ms 996 KB Output is correct
8 Correct 2 ms 1112 KB Output is correct
9 Correct 3 ms 1048 KB Output is correct
10 Correct 3 ms 992 KB Output is correct
11 Correct 3 ms 992 KB Output is correct
12 Correct 3 ms 996 KB Output is correct
13 Correct 3 ms 984 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 3 ms 996 KB Output is correct
11 Correct 4 ms 1180 KB Output is correct
12 Correct 3 ms 1192 KB Output is correct
13 Correct 3 ms 992 KB Output is correct
14 Correct 3 ms 1000 KB Output is correct
15 Correct 3 ms 1192 KB Output is correct
16 Correct 3 ms 988 KB Output is correct
17 Correct 3 ms 1000 KB Output is correct
18 Correct 2 ms 1036 KB Output is correct
19 Correct 2 ms 1000 KB Output is correct
20 Correct 2 ms 1032 KB Output is correct
21 Correct 3 ms 1000 KB Output is correct
22 Correct 3 ms 1004 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 2 ms 996 KB Output is correct
8 Correct 2 ms 1112 KB Output is correct
9 Correct 3 ms 1048 KB Output is correct
10 Correct 3 ms 992 KB Output is correct
11 Correct 3 ms 992 KB Output is correct
12 Correct 3 ms 996 KB Output is correct
13 Correct 3 ms 984 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 456 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 3 ms 996 KB Output is correct
24 Correct 4 ms 1180 KB Output is correct
25 Correct 3 ms 1192 KB Output is correct
26 Correct 3 ms 992 KB Output is correct
27 Correct 3 ms 1000 KB Output is correct
28 Correct 3 ms 1192 KB Output is correct
29 Correct 3 ms 988 KB Output is correct
30 Correct 3 ms 1000 KB Output is correct
31 Correct 2 ms 1036 KB Output is correct
32 Correct 2 ms 1000 KB Output is correct
33 Correct 2 ms 1032 KB Output is correct
34 Correct 3 ms 1000 KB Output is correct
35 Correct 3 ms 1004 KB Output is correct
36 Correct 1 ms 612 KB Output is correct
37 Correct 0 ms 356 KB Output is correct
38 Correct 1 ms 1260 KB Output is correct
39 Correct 2 ms 1260 KB Output is correct
40 Correct 1 ms 1004 KB Output is correct
41 Correct 1 ms 1264 KB Output is correct
42 Correct 1 ms 1260 KB Output is correct
43 Correct 1 ms 1256 KB Output is correct
44 Correct 1 ms 1272 KB Output is correct
45 Correct 1 ms 1004 KB Output is correct
46 Correct 1 ms 1260 KB Output is correct
47 Correct 1 ms 1260 KB Output is correct
48 Correct 1 ms 1260 KB Output is correct
49 Correct 1 ms 360 KB Output is correct
50 Correct 1 ms 360 KB Output is correct
51 Correct 0 ms 360 KB Output is correct
52 Correct 0 ms 360 KB Output is correct
53 Correct 0 ms 360 KB Output is correct
54 Correct 2 ms 1008 KB Output is correct
55 Correct 2 ms 1008 KB Output is correct
56 Correct 3 ms 996 KB Output is correct
57 Correct 3 ms 1192 KB Output is correct
58 Correct 3 ms 1008 KB Output is correct
59 Correct 4 ms 1008 KB Output is correct
60 Correct 3 ms 996 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 0 ms 348 KB Output is correct
63 Correct 0 ms 348 KB Output is correct
64 Correct 1 ms 348 KB Output is correct
65 Correct 3 ms 992 KB Output is correct
66 Correct 3 ms 996 KB Output is correct
67 Correct 3 ms 996 KB Output is correct
68 Correct 3 ms 996 KB Output is correct
69 Correct 2 ms 1176 KB Output is correct
70 Correct 2 ms 996 KB Output is correct
71 Correct 4 ms 996 KB Output is correct
72 Correct 0 ms 596 KB Output is correct
73 Correct 1 ms 348 KB Output is correct