oj.uz

Submission #1055507

# Submission time Handle Problem Language Result Execution time Memory
1055507 2024-08-12T20:27:42 Z oscar1f Lamps (JOI19_lamps) C++17
0 / 100
 189 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int TAILLE_MAX=(1<<18);
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 and pos<(1<<taille) and 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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Runtime error 189 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Runtime error 189 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Runtime error 166 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Runtime error 189 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -