oj.uz

Submission #1031563

# Submission time Handle Problem Language Result Execution time Memory
1031563 2024-07-23T00:58:04 Z Gabriel Vrtić (COCI18_vrtic) C++17
0 / 160
 787 ms 596 KB 
#include "bits/stdc++.h"
using namespace std;
vector<int> Grafo, Dulces;
vector<bool> Visitados;
int n;
mt19937 Aleatorio(2);
int Costo(vector<int> Asignado){
    int Retorno = 0;
    for(int i = 0; i < n; i++){
        int Dulce_1 = Dulces[Asignado[i]];
        int Dulce_2 = Dulces[Asignado[Grafo[i]]];
        int Disconformidad = abs(Dulce_1 - Dulce_2);
        Retorno = max(Retorno, Disconformidad);
    }
    return Retorno;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    Grafo.assign(n, 0);
    Dulces.assign(n, 0);
    Visitados.assign(n, 0);
    for(int i = 0; i < n; i++) cin>>Grafo[i];
    for(int i = 0; i < n; i++){
        cin>>Dulces[i];
        Grafo[i]--;
    }
    double Temperatura = 1000000;
    double Enfriador = 0.99999;
    vector<int> Asignar(n);
    for(int i = 0; i < n; i++) Asignar[i] = i;
    uniform_int_distribution<int> Entero(0, n - 1);
    uniform_real_distribution<double> Decimal(0, 1);
    int Costo_anterior = Costo(Asignar);
    while(Temperatura > 0.000001){
        int _1 = Entero(Aleatorio);
        int _2 = Entero(Aleatorio);
        vector<int> Copia = Asignar;
        swap(Copia[_1], Copia[_2]);
        int Nuevo = Costo(Copia);
        if(Nuevo < Costo_anterior){
            Costo_anterior = Nuevo;
            Asignar = Copia;
        } else {
            double Exponente = (double)abs(Nuevo - Costo_anterior);
            Exponente *= -1;
            Exponente /= Temperatura;
            if(exp(Exponente) > Decimal(Aleatorio)){
                Costo_anterior = Nuevo;
                Asignar = Copia;
            }
        }
        Temperatura *= Enfriador;
        /*cout<<Costo_anterior<<"\n";
        for(auto E: Asignar) cout<<Dulces[E]<<" ";
        cout<<"\n"<<Temperatura<<"\n";*/
    }
    cout<<Costo(Asignar)<<"\n";
    for(int i = 0; i < n; i++){
        cout<<Dulces[Asignar[i]]<<" ";
    }
    return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 431 ms 344 KB jury has better answer
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 777 ms 432 KB jury has better answer
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 316 ms 436 KB jury has better answer
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 305 ms 592 KB jury has better answer
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 305 ms 432 KB jury has better answer
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 602 ms 436 KB jury has better answer
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 723 ms 344 KB jury has better answer
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 756 ms 592 KB jury has better answer
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 787 ms 596 KB jury has better answer
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 777 ms 348 KB jury has better answer
2 Halted 0 ms 0 KB -