oj.uz

Submission #173686

# Submission time Handle Problem Language Result Execution time Memory
173686 2020-01-04T23:36:51 Z dessertion Akvizna (COCI19_akvizna) C++14
0 / 130
 860 ms 632 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-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;
    
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 807 ms 380 KB Output is correct
2 Correct 671 ms 376 KB Output is correct
3 Incorrect 546 ms 380 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 818 ms 476 KB Output is correct
2 Correct 705 ms 376 KB Output is correct
3 Incorrect 549 ms 380 KB Output isn't correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 860 ms 504 KB Output is correct
2 Incorrect 706 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 584 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 609 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 579 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

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

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 655 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 644 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

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

Subtask #22
0 / 5.0

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

Subtask #23
0 / 5.0

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

Subtask #24
0 / 5.0

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

Subtask #25
0 / 5.0

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

Subtask #26
0 / 5.0

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