제출 #235693

#제출 시각아이디문제언어결과실행 시간메모리
235693Charis02Lamps (JOI19_lamps)C++14
6 / 100
296 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() { 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 > cc = q.front(); q.pop(); int cur = cc.first; int used = cc.second; int tmp = cur; 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)); } } } 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)); } } } } 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][used]+1; q.push(mp(tmp,1)); } } } } 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...