Submission #235405

#TimeUsernameProblemLanguageResultExecution timeMemory
235405Charis02Lamps (JOI19_lamps)C++14
6 / 100
305 ms6868 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]; int steps[N]; void solve() { queue < int > q; int ss = 0; rep(i,0,n) ss += (s[i]-'0')*(1 << i); q.push(ss); vis[ss]=true; steps[ss] = 0; while(!q.empty()) { int cur = q.front(); q.pop(); int tmp = cur; rep(i,0,n) { tmp = cur; rep(j,i,n) { tmp |= (1 << j); if(!vis[tmp]) { vis[tmp]=true; steps[tmp]=steps[cur]+1; q.push(tmp); } } } rep(i,0,n) { tmp = cur; rep(j,i,n) { tmp &= ~(1 << j); if(!vis[tmp]) { vis[tmp]=true; steps[tmp]=steps[cur]+1; q.push(tmp); } } } rep(i,0,n) { tmp = cur; rep(j,i,n) { tmp ^= (1 << j); if(!vis[tmp]) { vis[tmp]=true; steps[tmp]=steps[cur]+1; q.push(tmp); } } } } 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 << steps[tt]; 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...