Submission #1064431

#TimeUsernameProblemLanguageResultExecution timeMemory
1064431ThylOneLamps (JOI19_lamps)C++14
0 / 100
1067 ms98392 KiB
//#################### //Lamps //#################### #include <algorithm> #include<bits/stdc++.h> using namespace std; string A,B; const int inf = 2*1e6; #define SET0 0 #define SET1 1 #define FLIP 2 #define pb push_back vector<int> desciption(int s0, int s1, int flip,int order_set){ vector<int> d; if(s0)d.pb(SET0); if(s1)d.pb(SET1); if(order_set==0 && d.size()==2)swap(d[0],d[1]); if(flip){ if(flip&1){ d.pb(FLIP); }else{ reverse(d.begin(),d.end()); d.pb(FLIP); reverse(d.begin(),d.end()); } } return d; } int tcost(vector<int> a,vector<int> b){ int cost = b.size(); for(int i = 0;i<min(b.size(),a.size());i++){ if(b[i]!=a[i])break; cost--; } return cost; } bool apply(vector<int> d,bool v){ for(int i:d){ if(i==SET0)v=0; if(i==SET1)v=1; if(i==FLIP)v^=1; } return v; } void dbg(vector<int> d){ for(int i:d){ if(i==SET0)cout<<"set0 ;"; if(i==SET1)cout<<"set1 ;"; if(i==FLIP)cout<<"flip ;"; } cout<<endl; } signed main(){ ios::sync_with_stdio(false); cin.tie(); int n; cin >> n; cin >> A >> B; int dp[n+1][2][2][3][2]; for(int s1=0;(int)s1<2;s1++) for(int s0=0;s0<2;s0++) for(int p=0;p<2;p++) for(int f=0;f<3;f++){ dp[n][s0][s1][f][p]=0; } for(int pos = n-1;pos>=0;pos--){ for(int s1=0;(int)s1<2;s1++) for(int s0=0;s0<2;s0++) for(int p=0;p<2;p++) for(int f=0;f<3;f++){ dp[pos][s0][s1][f][p] = 2*n+1; for(int ts1=0;(int)ts1<2;ts1++) for(int ts0=0;ts0<2;ts0++) for(int tp=0;tp<2;tp++) for(int tf=0;tf<3;tf++){ vector<int> a = desciption(s0, s1, f,p); vector<int> b = desciption(ts0, ts1, tf,tp); if(apply(b,(bool)(A[pos]-'0'))!=(bool)(B[pos]-'0')) continue; int c = tcost(a,b); int re = c+dp[pos+1][ts0][ts1][tf][tp]; dp[pos][s0][s1][f][p] = min(dp[pos][s0][s1][f][p],re); } } } cout<<dp[0][0][0][0][0]<<endl; return 0; };

Compilation message (stderr)

lamp.cpp: In function 'int tcost(std::vector<int>, std::vector<int>)':
lamp.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   34 |     for(int i = 0;i<min(b.size(),a.size());i++){
      |                   ~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...