Submission #1055514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055514		oscar1f	Lamps (JOI19_lamps)	C++17	0 / 100	222 ms	262144 KiB

lamp

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int TAILLE_MAX=(1<<19);
int taille,init,obj,distCour,longueur;
char carac;
int dist[TAILLE_MAX];
deque<int> enCours;

int tout1(int deb,int fin) {
    return (1<<(fin+1))-(1<<deb);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    for (int i=0;i<TAILLE_MAX;i++) {
        dist[i]=-1;
    }
    cin>>taille;
    for (int i=0;i<taille;i++) {
        cin>>carac;
        if (carac=='1') {
            init+=(1<<i);
        }
    }
    for (int i=0;i<taille;i++) {
        cin>>carac;
        if (carac=='1') {
            obj+=(1<<i);
        }
    }
    enCours.push_back(init);
    int pos;
    while (!enCours.empty()) {
        longueur=enCours.size();
        for (int i=0;i<longueur;i++) {
            pos=enCours.front();
            enCours.pop_front();
            if (pos<0 or pos>=(1<<taille)) {
                cout<<-1<<endl;
                return 0;
            }
            if (dist[pos]==-1) {
                dist[pos]=distCour;
                for (int deb=0;deb<taille;deb++) {
                    for (int fin=deb;fin<taille;fin++) {
                        enCours.push_back(pos^(tout1(deb,fin)));
                        enCours.push_back(pos|(tout1(deb,fin)));
                        enCours.push_back((pos|(tout1(deb,fin)))-tout1(deb,fin));
                    }
                }
            }
        }
        distCour++;
    }
    cout<<dist[obj]<<endl;
    return 0;
}
 

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 4
• Subtask 4: 0 / 49