This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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-4,alpha=0.8;
const int iterations = 1e5;
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;
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);
//SA
while(temp>ftemp){
//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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |