oj.uz

Submission #173674

# Submission time Handle Problem Language Result Execution time Memory
173674 2020-01-04T23:28:45 Z dessertion Akvizna (COCI19_akvizna) C++14
0 / 130
 687 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=5e-5,alpha=0.75;
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;
    
    //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.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 683 ms 504 KB Output is correct
2 Incorrect 586 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 669 ms 504 KB Output is correct
2 Incorrect 540 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 444 ms 476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #9
0 / 5.0

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

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 441 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 416 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 420 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #19
0 / 5.0

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

Subtask #21
0 / 5.0

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

Subtask #22
0 / 5.0

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

Subtask #23
0 / 5.0

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

Subtask #24
0 / 5.0

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

Subtask #25
0 / 5.0

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

Subtask #26
0 / 5.0

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