oj.uz

Submission #793660

# Submission time Handle Problem Language Result Execution time Memory
793660 2023-07-26T05:15:37 Z 반딧불(#10057) Flip it and Stick it (CCO23_day2problem1) C++17
18 / 25
 8 ms 3052 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 1e9;

struct minSegTree{
    int tree[800002];

    void init(int i, int l, int r){
        tree[i] = INF;
        if(l==r) return;
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
    }

    void update(int i, int l, int r, int x, int y){
        if(l==r){
            tree[i] = min(tree[i], y);
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, y);
        else update(i*2+1, m+1, r, x, y);
        tree[i] = min(tree[i*2], tree[i*2+1]);
    }

    int query(int i, int l, int r, int s, int e){
        if(r<s || e<l) return INF;
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return min(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }
} minTree;

int n;
int arr[200002];
int k;
int b[4];

void input();
void solvek1();
void solvek2();
void solvek3();

int main(){
    input();
    if(k==1) solvek1();
    if(k==2) solvek2();
    if(k==3) solvek3();
}

void input(){
    string str;
    cin >> str;
    n = (int)str.size();
    for(int i=1; i<=n; i++) arr[i] = (str[i-1] - '0');

    cin >> str;
    k = (int)str.size();
    for(int i=1; i<=k; i++) b[i] = (str[i-1] - '0');
}

void solvek1(){
    if(count(arr+1, arr+n+1, b[1])) printf("-1");
    else printf("0");
    exit(0);
}

void solvek2(){
    int ans = 0;
    if(b[1] != b[2]){
        int l = b[2], r = b[1];
        vector<int> v;
        for(int i=1; i<=n; i++){
            if(v.empty() || v.back() != arr[i]) v.push_back(arr[i]);
        }
        if(!v.empty() && v.back() == r) v.pop_back();
        if(!v.empty() && v[0] == l) v.erase(v.begin());
        ans = (int)v.size()/2;
    }
    else{
        int x = b[1];
        if(count(arr+1, arr+n+1, x) > (n+1)/2) ans = -1;
        else{
            for(int i=1; i<n; i++) if(arr[i] == x && arr[i+1] == x) ans++;
        }
    }
    printf("%d", ans >= n*2 ? -1 : ans);
}

void solve001(){
    int zeroCnt = 0, ans = 0;
    for(int i=1; i<=n; i++){
        if(arr[i] == 0){
            zeroCnt++;
            continue;
        }
        if(zeroCnt <= 1){
            zeroCnt = max(zeroCnt-1, 0);
            continue;
        }
        int j = i;
        while(j<n){
            if(arr[j+1] == 1 || j+1==n) j++;
            else if(arr[j+2] == 1) j+=2;
            else break;
        }
        ans++;
        zeroCnt = max(zeroCnt-1, 0);
        i=j;
    }
    printf("%d", ans);
}

void solve010(){
    int cnt = 0;
    for(int i=2; i<n; i++){
        if(arr[i-1] == 0 && arr[i] == 1 && arr[i+1] == 0) cnt++;
    }
    printf("%d", (cnt+1)/2);
}

void solve000(){
    if(count(arr+1, arr+n+1, 0) > n - n/3){
        puts("-1");
        return;
    }
    priority_queue<int> pq;
    int one = 0;
    int lim = 1;
    for(int i=1; i<=n; i++){
        if(arr[i] == 1){
            lim++;
            continue;
        }
        else{
            int j = i;
            while(j<n && arr[j+1] == 0) j++;
            pq.push(j-i+1);
            i=j;
        }
    }
    int ans = 0;
    while(!pq.empty() && pq.top() > 2){
        int x = pq.top();
        ans++;
        if(x > 3){ /// 3 �̻��̸� �����ϸ� 2 ���°� ������ �̵�
            if((int)pq.size() + one < lim){
                pq.pop();
                pq.push(x-2);
                pq.push(2);
            }
            else{ /// �ȵǸ� 1�̶� �� ���
                assert(one);
                one--;
                pq.pop();
                pq.push(x-1);
                pq.push(2);
            }
        }
        else{ /// 3�̸� 1 ������ 1�̶� �ϴ� �� �̵�
            if(one){
                one--;
                pq.pop();
                pq.push(x-1);
                pq.push(2);
            }
            else{
                pq.pop();
                pq.push(x-2);
                pq.push(2);
            }
        }
    }
    printf("%d", ans);
}

void solvek3(){
    if(b[1] != b[3]){ /// 001 ����
        if(b[1] != b[2]) reverse(arr+1, arr+n+1), reverse(b+1, b+k+1);
        if(b[1] != 0){
            for(int i=1; i<=n; i++) arr[i] = !arr[i];
            for(int i=1; i<=k; i++) b[i] = !b[i];
        }
        solve001();
    }
    else if(b[1] != b[2]){ /// 010 ����
        if(b[1] != 0){
            for(int i=1; i<=n; i++) arr[i] = !arr[i];
            for(int i=1; i<=k; i++) b[i] = !b[i];
        }
        solve010();
    }
    else{
        if(b[1] != 0){
            for(int i=1; i<=n; i++) arr[i] = !arr[i];
            for(int i=1; i<=k; i++) b[i] = !b[i];
        }
        solve000();
    }
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 1380 KB Output is correct
4 Correct 4 ms 1380 KB Output is correct
5 Correct 4 ms 1380 KB Output is correct
6 Correct 3 ms 1380 KB Output is correct
7 Correct 3 ms 1380 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 1 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 4 ms 1380 KB Output is correct
7 Correct 4 ms 1432 KB Output is correct
8 Correct 4 ms 2332 KB Output is correct
9 Correct 4 ms 1832 KB Output is correct
10 Correct 4 ms 1832 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 1 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 4 ms 1380 KB Output is correct
7 Correct 4 ms 1432 KB Output is correct
8 Correct 4 ms 2332 KB Output is correct
9 Correct 4 ms 1832 KB Output is correct
10 Correct 4 ms 1832 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 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 4 ms 1380 KB Output is correct
21 Correct 5 ms 1372 KB Output is correct
22 Correct 4 ms 2332 KB Output is correct
23 Correct 6 ms 1832 KB Output is correct
24 Correct 5 ms 1772 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 4 ms 1380 KB Output is correct
27 Correct 5 ms 1380 KB Output is correct
28 Correct 4 ms 1380 KB Output is correct
29 Correct 4 ms 1380 KB Output is correct
30 Correct 4 ms 1396 KB Output is correct
31 Correct 4 ms 1380 KB Output is correct
32 Correct 4 ms 1380 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 4 ms 1380 KB Output is correct
8 Correct 4 ms 1380 KB Output is correct
9 Correct 4 ms 1380 KB Output is correct
10 Correct 3 ms 1380 KB Output is correct
11 Correct 4 ms 1380 KB Output is correct
12 Correct 4 ms 1380 KB Output is correct
13 Correct 5 ms 1380 KB Output is correct

Subtask #5
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 1 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 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 4 ms 1380 KB Output is correct
11 Correct 4 ms 1340 KB Output is correct
12 Correct 4 ms 1380 KB Output is correct
13 Correct 4 ms 1324 KB Output is correct
14 Correct 4 ms 1380 KB Output is correct
15 Correct 4 ms 1380 KB Output is correct
16 Correct 6 ms 1380 KB Output is correct
17 Correct 4 ms 1380 KB Output is correct
18 Correct 4 ms 1380 KB Output is correct
19 Correct 4 ms 1364 KB Output is correct
20 Correct 4 ms 1380 KB Output is correct
21 Correct 4 ms 1372 KB Output is correct
22 Correct 4 ms 1380 KB Output is correct

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 4 ms 1380 KB Output is correct
8 Correct 4 ms 1380 KB Output is correct
9 Correct 4 ms 1380 KB Output is correct
10 Correct 3 ms 1380 KB Output is correct
11 Correct 4 ms 1380 KB Output is correct
12 Correct 4 ms 1380 KB Output is correct
13 Correct 5 ms 1380 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 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 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 4 ms 1380 KB Output is correct
24 Correct 4 ms 1340 KB Output is correct
25 Correct 4 ms 1380 KB Output is correct
26 Correct 4 ms 1324 KB Output is correct
27 Correct 4 ms 1380 KB Output is correct
28 Correct 4 ms 1380 KB Output is correct
29 Correct 6 ms 1380 KB Output is correct
30 Correct 4 ms 1380 KB Output is correct
31 Correct 4 ms 1380 KB Output is correct
32 Correct 4 ms 1364 KB Output is correct
33 Correct 4 ms 1380 KB Output is correct
34 Correct 4 ms 1372 KB Output is correct
35 Correct 4 ms 1380 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 1380 KB Output is correct
39 Runtime error 8 ms 3052 KB Execution killed with signal 6
40 Halted 0 ms 0 KB -