QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#872652#8614. 3Ducup-team055#WA 1785ms4096kbC++175.3kb2025-01-26 03:14:472025-01-26 03:14:47

Judging History

你现在查看的是最新测评结果

  • [2025-01-26 03:14:47]
  • 评测
  • 测评结果:WA
  • 用时:1785ms
  • 内存:4096kb
  • [2025-01-26 03:14:47]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
const ll ILL=2167167167167167167;
const int INF=2100000000;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
template<class T> using _pq = priority_queue<T, vector<T>, greater<T>>;
template<class T> int LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> int UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> bool chmin(T &a,T b){if(b<a){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}
template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}
bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;}
template<class T> void vec_out(vector<T> &p,int ty=0){
    if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'<<p[i]<<'"';}cout<<"}\n";}
    else{if(ty==1){cout<<p.size()<<"\n";}for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}}
template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;}
template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;}
template<class T> T vec_sum(vector<T> &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;}
int pop_count(long long a){int res=0;while(a){res+=(a&1),a>>=1;}return res;}
template<class T> T square(T a){return a * a;}

//https://ei1333.github.io/library/other/xor-shift.cpp.html
struct XorShift {
private:
    constexpr static double R = 1.0 / 0xffffffff;
    uint64_t x;

public:
    explicit XorShift(uint64_t seed = 88172645463325252ull) : x(seed) {}

    template< typename T = uint64_t >
    inline T get() { // [0, 2^64)
        x ^= x << 7ull;
        x ^= x >> 9ull;
        return x;
    }

    inline uint32_t get(uint32_t r) { // [0, r)
        return ((uint64_t) get< uint32_t >() * r) >> 32ull;
    }

    inline uint32_t get(uint32_t l, uint32_t r) { // [l, r)
        return l + get(r - l);
    }

    inline double probability() { // [0.0, 1.0]
        return get< uint32_t >() * R;
    }
};

struct point {
    ld x = 0.5;
    ld y = 0.5;
    ld z = 0.5;
};

ld dist(point a, point b){
    return hypot(a.x - b.x, a.y - b.y, a.z - b.z);
}

point add(point a, point b){
    a.x += b.x;
    a.y += b.y;
    a.z += b.z;
    chmin(a.x, (ld)(1));
    chmax(a.x, (ld)(0));
    chmin(a.y, (ld)(1));
    chmax(a.y, (ld)(0));
    chmin(a.z, (ld)(1));
    chmax(a.z, (ld)(0));
    return a;
}

vector<vector<ld>> make(int N, int seed = 0){
    vector<point> a(N);
    XorShift table(seed);
    rep(i, 0, N){
        a[i].x = table.probability();
        a[i].y = table.probability();
        a[i].z = table.probability();
    }
    vector res(N, vector<ld>(N));
    rep(i, 0, N) rep(j, 0, N){
        if (i > j) res[i][j] = res[j][i];
        else if (i == j) res[i][j] = 0;
        else res[i][j] = dist(a[i], a[j]) + table.probability() * (ld)(0.2) - (ld)(0.1);
    }
    return res;
}

void solve();
// CITRUS CURIO CITY / FREDERIC
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;
    rep(i, 0, t) solve();
}

void solve(){
    const int local = false;
    int N;
    cin >> N;
    vector D(N, vector<ld>(N));
    if (local){
        int seed;
        cin >> seed;
        D = make(N, seed);
    }
    else{
        rep(i, 0, N) rep(j, 0, N) cin >> D[i][j];
    }
    auto calc_score = [&](vector<point> a) -> ld {
        ld sum = 0;
        rep(i, 0, N) rep(j, 0, i){
            ld tmp = dist(a[i], a[j]) - D[i][j];
            sum += tmp * tmp;
        }
        return sum;
    };
    int st = clock();
    XorShift table;
    double start_temp = 0.001;
    double end_temp = 0.0001;
    ld delta = 100;
    double TL = 1900000;
    vector<point> ans(N);
    auto best = ans;
    ld best_score = calc_score(ans);
    while (true){
        double now_time = clock() - st;
        if (now_time > TL) break;
        int ind = table.get(N);
        point ad;
        ad.x = table.probability() - 0.5;
        ad.y = table.probability() - 0.5;
        ad.z = table.probability() - 0.5;
        ld nor = hypot(ad.x, ad.y, ad.z);
        nor *= delta;
        ad.x /= nor, ad.y /= nor, ad.z /= nor;
        auto n_ans = ans;
        n_ans[ind] = add(n_ans[ind], ad);
        ld diff = calc_score(ans) - calc_score(n_ans);
        double temp = start_temp + (end_temp - start_temp) * now_time / TL;
        if (exp(diff / temp) > table.probability()){
            swap(n_ans, ans);
            if (chmin(best_score, calc_score(ans))){
                best = ans;
            }
        }
    }
    ans = best;
    rep(i, 0, N){
        cout << fixed << setprecision(20) << ans[i].x << " " << ans[i].y << " " << ans[i].z << "\n";
    }
    if (local){
        ld diff_max = 0;
        rep(i, 0, N) rep(j, 0, i){
                chmax(diff_max, abs(dist(ans[i], ans[j]) - D[i][j]));
        }
        cout << "diff max : " << diff_max << "\n";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1562ms
memory: 4096kb

input:

4
0.000000 0.758400 0.557479 0.379026
0.758400 0.000000 0.516608 0.446312
0.557479 0.516608 0.000000 0.554364
0.379026 0.446312 0.554364 0.000000

output:

0.07786673737083602794 0.16934603371210773697 0.66832862626468482513
0.57013362887972953607 0.64866823695692890845 0.35014006322572989899
0.42467208283842827288 0.57208979717028110286 0.84111919967386701146
0.25585781164463951612 0.33044080934300574981 0.37364158869792694567

result:

ok OK. Max delta: 0.001709

Test #2:

score: 0
Accepted
time: 1175ms
memory: 4096kb

input:

1
0.000000

output:

0.50000000000000000000 0.50000000000000000000 0.50000000000000000000

result:

ok OK. Max delta: 0.000000

Test #3:

score: 0
Accepted
time: 1385ms
memory: 4096kb

input:

2
0.000000 0.938096
0.938096 0.000000

output:

0.68847730550198998689 0.38468494348348147567 0.21507410066200712462
0.13780666096792321628 0.27571403296779986515 0.96667993163662424989

result:

ok OK. Max delta: 0.000000

Test #4:

score: 0
Accepted
time: 1453ms
memory: 4096kb

input:

3
0.000000 0.769195 0.308169
0.769195 0.000000 0.686850
0.308169 0.686850 0.000000

output:

0.33351056702062294274 0.79425188083181746490 0.69933100662996347915
0.94761953995594066727 0.40364429368489319961 0.45069521015766317637
0.48624331738196033490 0.62647843347501488834 0.90798183070388513921

result:

ok OK. Max delta: 0.000094

Test #5:

score: 0
Accepted
time: 1633ms
memory: 4096kb

input:

5
0.000000 0.444506 0.292333 0.209539 1.195824
0.444506 0.000000 0.220873 0.748833 0.757486
0.292333 0.220873 0.000000 0.533499 0.797167
0.209539 0.748833 0.533499 0.000000 1.141148
1.195824 0.757486 0.797167 1.141148 0.000000

output:

0.98785461277910122612 0.21510584745846121582 0.54971983819945568177
0.93243189237315718019 0.59430736813426679113 0.22479756124424034713
0.85808008823116105898 0.46487040498294391233 0.37571921247968613161
0.83047275762164378198 0.07282428764872587656 0.68990604397352468287
0.23210581425676112447 0...

result:

ok OK. Max delta: 0.076914

Test #6:

score: 0
Accepted
time: 1646ms
memory: 4096kb

input:

6
0.000000 0.932377 0.787009 0.996894 0.763544 0.651377
0.932377 0.000000 0.421278 1.155673 1.149686 0.508563
0.787009 0.421278 0.000000 0.709021 0.793974 0.224884
0.996894 1.155673 0.709021 0.000000 0.392548 0.957498
0.763544 1.149686 0.793974 0.392548 0.000000 0.714079
0.651377 0.508563 0.224884 0...

output:

0.16108058083086760361 0.80079810577489635056 0.97914251957794750134
0.00000000000000000000 0.81132295909239882613 0.06148627160477080982
0.37645110238985856466 0.69969776016099575013 0.23623908885297268722
0.77933930158883450376 0.13312692267372446370 0.56368746118488978047
0.82448395620338552780 0...

result:

ok OK. Max delta: 0.059448

Test #7:

score: 0
Accepted
time: 1696ms
memory: 4096kb

input:

7
0.000000 0.688481 0.455407 0.777049 0.963980 0.255052 0.554599
0.688481 0.000000 0.596921 0.827787 1.260207 0.340235 0.493011
0.455407 0.596921 0.000000 0.609173 0.640567 0.352193 0.243913
0.777049 0.827787 0.609173 0.000000 0.858134 0.701131 0.393303
0.963980 1.260207 0.640567 0.858134 0.000000 0...

output:

0.36177543269700639201 0.52137518390680122511 0.98942251355555211240
0.85059626318313737034 0.92771873306101528548 0.82297292910783415688
0.45490057658749575420 0.57648173427834865917 0.53478806431555686156
0.87509258084510516465 0.15680451833770756671 0.52256962647259207867
0.11274629599115267458 0...

result:

ok OK. Max delta: 0.039361

Test #8:

score: 0
Accepted
time: 1736ms
memory: 4096kb

input:

8
0.000000 0.437494 0.934265 0.074097 0.673669 0.425700 0.479212 0.679270
0.437494 0.000000 0.331045 0.393801 0.527073 0.402792 0.375134 0.461133
0.934265 0.331045 0.000000 0.792317 0.605663 0.880433 0.786178 0.455534
0.074097 0.393801 0.792317 0.000000 0.681633 0.278020 0.327267 0.550058
0.673669 0...

output:

0.50361604429095643566 0.68257027417094148260 0.66316842795876836450
0.46576168371114237771 0.30421546949485936087 0.34838164646187189490
0.20386560742807718764 0.02781296063377972044 0.15029318481883985808
0.53019704696924187926 0.64776359884942095010 0.54764783133434926835
0.46117017290940445502 0...

result:

ok OK. Max delta: 0.098172

Test #9:

score: 0
Accepted
time: 1744ms
memory: 3968kb

input:

9
0.000000 0.883128 0.449200 0.525234 0.745161 0.323207 0.430759 1.247103 0.564870
0.883128 0.000000 0.664206 0.590150 0.433578 0.890708 0.741718 0.798316 1.033522
0.449200 0.664206 0.000000 0.326949 0.636800 0.523900 0.642051 0.680925 0.349474
0.525234 0.590150 0.326949 0.000000 0.523965 0.344241 0...

output:

0.06539464275253800323 0.24976980021977496587 0.42290140890233287674
0.73599132836886252000 0.80698452864601271549 0.24140525634083796671
0.42095892886558309483 0.40356938245978300520 0.74290975718914522110
0.52957103292931323864 0.34464224784266993002 0.44253030696720100417
0.38515809808826049712 0...

result:

ok OK. Max delta: 0.075844

Test #10:

score: 0
Accepted
time: 1781ms
memory: 3968kb

input:

10
0.000000 1.141963 0.357381 0.960442 0.887799 0.393165 1.000015 0.883861 1.059968 0.666258
1.141963 0.000000 0.730979 0.430440 0.528721 0.822481 0.567380 0.334929 0.552413 0.840500
0.357381 0.730979 0.000000 0.861027 0.623726 0.216981 0.719423 0.558824 0.726378 0.310217
0.960442 0.430440 0.861027 ...

output:

0.43205991270380170145 0.07036339201957265255 0.91835264783005533557
0.59380462036221453383 0.78734990220518652709 0.07449921753793705290
0.36135573993083586601 0.27316654612797462983 0.60485227240231318141
0.98343743444510092343 0.68096006858685335147 0.33094130663407495145
0.40707387678631838063 0...

result:

ok OK. Max delta: 0.091211

Test #11:

score: 0
Accepted
time: 1769ms
memory: 4096kb

input:

10
0.000000 0.508467 0.359704 0.705660 0.752608 0.632298 0.433047 0.541855 0.108842 0.652503
0.508467 0.000000 0.849608 0.542157 0.614068 0.673963 0.552462 0.470005 0.697815 0.822930
0.359704 0.849608 0.000000 0.832286 0.790254 0.844729 0.428335 0.707356 0.221649 0.447522
0.705660 0.542157 0.832286 ...

output:

0.23739963958905089744 0.15685601768763390179 0.63403552709962085991
0.49629524136347065528 0.49947227212703667143 0.26884934746874164806
0.13083017634331589336 0.17366606690044672597 0.96395712912067843401
0.38183646800334920023 0.86715410852231650571 0.61636837790900809791
0.78021225735158404569 0...

result:

ok OK. Max delta: 0.081539

Test #12:

score: 0
Accepted
time: 1785ms
memory: 4096kb

input:

10
0.000000 0.532841 1.081715 0.791902 0.304710 0.943952 0.318604 0.512618 0.263399 0.317304
0.532841 0.000000 0.617254 0.571776 0.863445 0.644868 0.534570 0.898453 0.767957 0.380512
1.081715 0.617254 0.000000 0.498716 1.118400 0.375946 0.739541 1.081104 0.985516 0.778030
0.791902 0.571776 0.498716 ...

output:

0.94058400300100779588 0.52096129668750187962 0.47882922179784631251
0.60705039938796944018 0.34178639392771217387 0.02645825036012830563
0.02295869316387415392 0.56819426674688900352 0.01739113275740197100
0.21684502380590832007 0.28404515207265162137 0.39699940131051679478
0.92244060844677152586 0...

result:

ok OK. Max delta: 0.097852

Test #13:

score: 0
Accepted
time: 1778ms
memory: 3968kb

input:

10
0.000000 0.337812 0.820740 0.714576 0.958294 1.114603 1.052855 0.816204 0.921684 0.581533
0.337812 0.000000 0.588126 0.550959 0.851936 1.076003 0.824637 0.634512 0.630209 0.781504
0.820740 0.588126 0.000000 0.754545 0.853344 0.651402 0.625435 0.521290 0.463145 0.927492
0.714576 0.550959 0.754545 ...

output:

0.59054581552943574013 0.97899227421695950700 0.33458371780986480301
0.45914864896194735566 0.70993775412004312406 0.19088046251643570788
0.15245210079688841065 0.23711726570129563735 0.26136028410698944352
0.10093152607103613685 0.78162006198874638097 0.71020494337397804482
0.89936706362201669911 0...

result:

ok OK. Max delta: 0.086871

Test #14:

score: -100
Wrong Answer
time: 1784ms
memory: 3968kb

input:

10
0.000000 0.157221 0.630350 0.940948 0.790907 0.666502 0.536584 0.506196 0.353744 0.642539
0.157221 0.000000 0.582092 1.279081 0.812532 0.810677 0.850103 0.865478 0.320962 0.694578
0.630350 0.582092 0.000000 1.171965 1.045437 1.168568 0.582206 0.854963 0.513105 1.137099
0.940948 1.279081 1.171965 ...

output:

0.22386734075778716025 0.51909719874266757622 0.56334742151050453351
0.07965581278235378735 0.33957995602770254840 0.69815010007150788009
0.09468443214909320701 0.15318643358026418475 0.11376023042699681560
0.98878640059152392126 0.89025423723369622559 0.07855204107187302219
0.94952558829131090506 0...

result:

wrong answer Expected distance between 0 and 1 is 0.157221, but found 0.266824