Submission #1589405


Source Code Expand

/*
 ***
 Question Name:
 ***
 Question Link:
 
 ***
 Idea: The critial thing is an O(n logn) Algorithm to count the maximum length of the increasing subsequence.
 */

#include <memory.h>
#include <iomanip>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>

#define REP(i,s,n) for(int (i)=s; (i)<(int)(n);(i)++)
#define RIT(it,c) for(__typeof(c.begin()) it = c.begin();it!=c.end();it++)
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define MSET(m,v) memset(m,v,sizeof(m))

using namespace std;

typedef long long LL;
typedef long double LD;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<LL> vL;
typedef vector<bool> vb;
typedef unordered_set<int> ui;
typedef pair<LL,LL> pLL;

class ShiftAndFlip{
    void findLeftRight(vi &left, vi &right, string &B){
        int n = (int)B.size();
        left.resize(n);
        right.resize(n);
        string S = B + B + B;
        int l = 0;
        while(S[n-l] != '1') ++l;
        left[0] = l;
        for(int i=1;i<n;++i){
            if(S[n+i] != '1') left[i] = left[i-1] + 1;
            else left[i] = 0;
        }
        l = 0;
        while(S[n-1+l] != '1') ++l;
        right[n-1] = l;
        for(int i=n-2;i>=0;--i){
            if(S[n+i] != '1') right[i] = right[i+1] + 1;
            else right[i] = 0;
        }
        return;
    }
    int computeOp(string &A, string &B, int d, vi &left, vi &right){
        int n = (int)B.size(), cnt = 0;
        priority_queue<ii> l_list, r_list;
        vi nleft(n), nright(n);
        for(int i=0;i<n;++i) if(A[i] != B[(i+d+n)%n]){
            ++cnt;
            if(d>0){
                nleft[i] = left[i], nright[i] = max(0, right[i]-d);
            }
            else{
                nleft[i] = max(0, left[i] + d), nright[i] = right[i];
            }
            r_list.push(ii(nright[i],i));
        }
        if(r_list.empty()) return abs(d)+cnt;
        int ans = r_list.top().first;
        while(!r_list.empty()){
            int length = r_list.top().first;
            while (!r_list.empty() && r_list.top().first == length) {
                int j = r_list.top().second;
                r_list.pop();
                l_list.push(ii(nleft[j],j));
            }
            if(r_list.empty()) ans = min(ans, l_list.top().first);
            else ans = min(ans, l_list.top().first + r_list.top().first);
        }
        return abs(d) + 2*ans + cnt;
    }
public:
    int Solution(string &A, string &B){
        if(B.find('1') == string::npos) return A.find('1')==string::npos? 0:-1;
        vi left,right;
        findLeftRight(left, right, B);
        int n = (int)B.size();
        int ans = 3*n;
        for(int d=-n;d<=n;++d){
            ans = min(ans, computeOp(A, B, d, left, right));
        }
        return ans;
    }
    
};

int main(){
    string A,B;
    cin>>A>>B;
    cout<<ShiftAndFlip().Solution(A, B)<<endl;
    return 0;
}

Submission Info

Submission Time
Task D - Shift and Flip
User pkugoodspeed
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 3397 Byte
Status AC
Exec Time 754 ms
Memory 384 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 4
AC × 54
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
sample_04.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 1 ms 256 KB
subtask_1_03.txt AC 1 ms 256 KB
subtask_1_04.txt AC 1 ms 256 KB
subtask_1_05.txt AC 712 ms 384 KB
subtask_1_06.txt AC 1 ms 256 KB
subtask_1_07.txt AC 38 ms 256 KB
subtask_1_08.txt AC 1 ms 256 KB
subtask_1_09.txt AC 1 ms 256 KB
subtask_1_10.txt AC 2 ms 256 KB
subtask_1_11.txt AC 489 ms 256 KB
subtask_1_12.txt AC 528 ms 384 KB
subtask_1_13.txt AC 479 ms 384 KB
subtask_1_14.txt AC 400 ms 256 KB
subtask_1_15.txt AC 430 ms 256 KB
subtask_1_16.txt AC 460 ms 256 KB
subtask_1_17.txt AC 454 ms 256 KB
subtask_1_18.txt AC 466 ms 256 KB
subtask_1_19.txt AC 493 ms 384 KB
subtask_1_20.txt AC 471 ms 256 KB
subtask_1_21.txt AC 388 ms 256 KB
subtask_1_22.txt AC 387 ms 256 KB
subtask_1_23.txt AC 749 ms 384 KB
subtask_1_24.txt AC 754 ms 384 KB
subtask_1_25.txt AC 751 ms 384 KB
subtask_1_26.txt AC 2 ms 256 KB
subtask_1_27.txt AC 5 ms 256 KB
subtask_1_28.txt AC 17 ms 256 KB
subtask_1_29.txt AC 89 ms 256 KB
subtask_1_30.txt AC 403 ms 384 KB
subtask_1_31.txt AC 1 ms 256 KB
subtask_1_32.txt AC 2 ms 256 KB
subtask_1_33.txt AC 5 ms 256 KB
subtask_1_34.txt AC 22 ms 256 KB
subtask_1_35.txt AC 87 ms 256 KB
subtask_1_36.txt AC 398 ms 256 KB
subtask_1_37.txt AC 2 ms 256 KB
subtask_1_38.txt AC 5 ms 256 KB
subtask_1_39.txt AC 22 ms 256 KB
subtask_1_40.txt AC 90 ms 256 KB
subtask_1_41.txt AC 364 ms 256 KB
subtask_1_42.txt AC 358 ms 256 KB
subtask_1_43.txt AC 390 ms 256 KB
subtask_1_44.txt AC 402 ms 256 KB
subtask_1_45.txt AC 409 ms 256 KB
subtask_1_46.txt AC 410 ms 256 KB