oj.uz

답안 #173685

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
173685 2020-01-04T23:36:28 Z dessertion Akvizna (COCI19_akvizna) C++14
0 / 130
 420 ms 584 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 = 5e4;

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

# 결과 실행 시간 메모리 Grader output
1 Correct 405 ms 376 KB Output is correct
2 Correct 336 ms 504 KB Output is correct
3 Incorrect 274 ms 380 KB Output isn't correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 412 ms 376 KB Output is correct
2 Correct 359 ms 376 KB Output is correct
3 Incorrect 274 ms 376 KB Output isn't correct

Subtask #3
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 420 ms 376 KB Output is correct
2 Incorrect 355 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 397 ms 376 KB Output is correct
2 Incorrect 323 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 299 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 283 ms 388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 295 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 281 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 312 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 302 ms 508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 309 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 308 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 288 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 239 ms 500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 239 ms 580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 240 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 240 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 239 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 239 ms 584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 240 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 240 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #22
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 239 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #23
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 239 ms 500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #24
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 239 ms 496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #25
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 239 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #26
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 242 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -