oj.uz

Submission #173687

# Submission time Handle Problem Language Result Execution time Memory
173687 2020-01-04T23:37:24 Z dessertion Akvizna (COCI19_akvizna) C++14
15 / 130
 1057 ms 636 KB 
#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-5,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;
    
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1010 ms 376 KB Output is correct
2 Correct 838 ms 376 KB Output is correct
3 Correct 682 ms 388 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 376 KB Output is correct
2 Incorrect 882 ms 508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1057 ms 384 KB Output is correct
2 Correct 889 ms 504 KB Output is correct
3 Correct 717 ms 504 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 989 ms 384 KB Output is correct
2 Correct 796 ms 376 KB Output is correct
3 Correct 672 ms 420 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 791 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 746 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 784 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 725 ms 420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 822 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 794 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 843 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 833 ms 388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 758 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 589 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 588 ms 580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 589 ms 496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 620 ms 636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 587 ms 484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 587 ms 580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 590 ms 496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 588 ms 508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #22
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 588 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #23
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 590 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #24
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 588 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #25
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 589 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #26
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 592 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -