Submission #235406

#TimeUsernameProblemLanguageResultExecution timeMemory
235406Charis02Lamps (JOI19_lamps)C++14
0 / 100
1084 ms4984 KiB
#include<iostream> #include<stdio.h> #include<vector> #include<cmath> #include<queue> #include<string.h> #include<unordered_map> #include<set> #include<algorithm> #define ll int #define pi pair < ll,ll > #define mp(a,b) make_pair(a,b) #define mid (low+high)/2 #define rep(i,a,b) for(int i = a;i < b;i++) #define N 300004 #define INF 1e9+7 using namespace std; ll n; string s,t; bool vis[N][2]; int steps[N][2]; void solve() { rep(i,0,N) steps[i][0] = steps[i][1] = n; queue < pair < int,int > > q; int ss = 0; rep(i,0,n) ss += (s[i]-'0')*(1 << i); q.push(mp(ss,0)); vis[ss][0]=true; steps[ss][0] = 0; while(!q.empty()) { pair < int,int > top = q.front(); int cur = top.first; int used = top.second; q.pop(); int tmp = cur; rep(i,0,n) { tmp = cur; rep(j,i,n) { tmp |= (1 << j); if(!vis[tmp]) { vis[tmp][1]=true; steps[tmp][1]=steps[cur][1]+1; q.push(mp(tmp,1)); } } } rep(i,0,n) { tmp = cur; rep(j,i,n) { tmp &= ~(1 << j); if(!vis[tmp][1]) { vis[tmp][1]=true; steps[tmp][1]=steps[cur][1]+1; q.push(mp(tmp,1)); } } } if(used == 0) { rep(i,0,n) { tmp = cur; rep(j,i,n) { tmp ^= (1 << j); if(!vis[tmp][0]) { vis[tmp][0]=true; steps[tmp][0]=steps[cur][0]+1; q.push(mp(tmp,0)); } } } } } return; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; cin >> s; cin >> t; solve(); int tt=0; rep(i,0,n) tt += (t[i]-'0')*(1<<i); cout << min(steps[tt][0],steps[tt][1]); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...