Submission #173678

#	Time	Username	Problem	Language	Result	Execution time	Memory
173678		dessertion	새로운 문제 (COCI19_akvizna)	C++14	0 / 130	1570 ms	636 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pb_ push_back
#define eb_ emplace_back
#define mp_ make_pair
//#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<long,long> pll;
typedef pair<int,int> pii;

int N,K;
long double temp=1,ftemp=1e-2,alpha=0.75;
const int iterations = 5e5;

long double ans = 0;

vector<int> choices;

mt19937 mt(time(0));

bool roll(long double p){
    uniform_real_distribution<long double> dist(0,1);
    return dist(mt)<=p;
}

int ran(int a, int b){
    uniform_int_distribution<int> dist(a,b);
    return dist(mt);
}

int main(){
    cin.tie(0),cout.tie(0),ios::sync_with_stdio(0);
    cin>>N>>K;
    
    //SA 
    while(temp>ftemp){
        long double cur=0;
        //random setup
        choices.clear();
        choices.pb_(1);
        for(int i = 1;i <K; i++){
            int sel = ran(choices.back()+1,N-(K-i)+1);
            cur+=1.0*(sel-choices.back())/(N-(choices.back()-1));
            choices.pb_(sel);
        }
        cur+=1.0*(N+1-choices.back())/(N-(choices.back()-1));
        choices.pb_(N+1);
        ans=max(ans,cur);
        
        //here is the hill climbing part
        for(int t = 0; t<iterations; t++){
            //we pick an index from 1 to K-1, and randomize its location
            int sel = ran(1,K-1);
            int one = choices[sel-1], two=choices[sel+1];
            int nxt = ran(one+1,two-1);
            long double nxtcur = cur-1.0*(choices[sel]-one)/(N-(one-1))-1.0*(two-choices[sel])/(N-(choices[sel]-1));
            nxtcur+=1.0*(nxt-one)/(N-(one-1))+1.0*(two-nxt)/(N-(nxt-1));
            
            ans=max(ans,nxtcur);
            if(nxtcur>=cur){
                cur=nxtcur;
                choices[sel]=nxt;
            }
            else{
                if(roll(exp(-(cur-nxtcur)/temp))){
                    //roll succeeds, do it anyways
                    cur=nxtcur;
                    choices[sel]=nxt;
                }
            }
        }
        temp*=alpha;
    }
    cout.precision(10);
    cout<<fixed<<ans<<endl;
    
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5
• Subtask 24: 0 / 5
• Subtask 25: 0 / 5
• Subtask 26: 0 / 5