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 |
|
|
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 |