제출 #1031552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1031552		Gabriel	Vrtić (COCI18_vrtic)	C++17	16 / 160	705 ms	600 KiB

vrtic

#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 = 100000;
    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: 16 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16