QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#871517#8614. 3Ducup-team6275#TL 727ms4096kbC++234.2kb2025-01-25 20:57:552025-01-25 20:57:57

Judging History

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

  • [2025-01-25 20:57:57]
  • 评测
  • 测评结果:TL
  • 用时:727ms
  • 内存:4096kb
  • [2025-01-25 20:57:55]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for (int i = 0; i < (n); i += 1)
#define len(a) ((int)(a).size())

mt19937_64 rnd(time(0));
mt19937 rndint(time(0) + 10);
const ll inf = 1e18;

const int SZ = 11;
const ld eps = 1e-9;
ld d[SZ][SZ];
int n;

struct pt {
    ld x, y, z;

    ld ln() {
        return sqrtl(x * x + y * y + z * z);
    }

    pt operator+(const pt &rht) {
        return {x + rht.x, y + rht.y, z + rht.z};
    }

    pt operator-(const pt &rht) {
        return {x - rht.x, y - rht.y, z - rht.z};
    }

    pt operator*(ld fuck) {
        return {x * fuck, y * fuck, z * fuck};
    }

    pt norm(ld a = 1) {
        ld nrm = a / ln();
        return {x * nrm, y * nrm, z * nrm};
    }
};
vector<pt> pts;

ld distsq(const pt &a, const pt &b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z);
}

ld dist(const pt &a, const pt &b) {
    return sqrtl(distsq(a, b));
}

ld get_random_ld() {
    const ll mod = 1e15;
    return rnd() % mod / (ld)(mod - 1);
}

int check(int v) {
    int res = 0;
    for (int i = 0; i < n; ++i) {
        if (i != v && abs(dist(pts[i], pts[v]) - d[i][v]) > 0.1 - eps)
            ++res;
    }
    return res;
}

int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }

    cin >> n;

#ifdef LOCAL
    vector<pt> genpts(n);
    for (int i = 0; i < n; ++i) {
        genpts[i].x = get_random_ld();
        genpts[i].y = get_random_ld();
        genpts[i].z = get_random_ld();
    }

    for (int i = 0; i < n; ++i) {
        d[i][i] = 0;
        for (int j = i + 1; j < n; ++j) {
            d[i][j] = dist(genpts[i], genpts[j]) - (get_random_ld() - 0.5) / 5;
            d[j][i] = d[i][j];
        }
    }

#else
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            cin >> d[i][j];
    }
#endif

    while (true) {
        pts.resize(n);
        vector<vector<ld>> ws(n, vector<ld>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                ws[i][j] = get_random_ld() + 5;
            }
        }
        for (int i = 0; i < n; ++i) {
            pts[i].x = get_random_ld();
            pts[i].y = get_random_ld();
            pts[i].z = get_random_ld();
        }

        int cnt_bad = 0;
        for (int i = 0; i < n; ++i)
            cnt_bad += check(i);

        cnt_bad /= 2;
        int iters = 0;

        bool fail = false;
        while (cnt_bad) {
            int v = rndint() % n;
            cnt_bad -= check(v);
            pt cur = {0, 0, 0};
            ld normed = 0;
            for (int i = 0; i < n; ++i) {
                if (i == v)
                    continue;

                pt yp = pts[i] + (pts[v] - pts[i]).norm(d[v][i]);

                cur = cur + yp * ws[i][v];
                normed += ws[i][v];
            }
            cur = cur * (1 / normed);
            pts[v] = cur;
            cnt_bad += check(v);

            if (iters % 100 == 0) {

                cnt_bad = 0;
                for (int i = 0; i < n; ++i) {
                    cnt_bad += check(i);
                }
                cnt_bad /= 2;
            }

            ++iters;
            if (iters >= 1000) {
                fail = true;
                break;
            }
        }

        if (fail)
            continue;

#ifdef LOCAL
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cout << setprecision(10) << fixed << dist(pts[i], pts[j]) << " ";
            }
            cout << "\n";
        }
#endif

        pt avg = {0, 0, 0};
        for (auto c : pts) {
            avg = avg + c;
        }
        avg.x /= n;
        avg.y /= n;
        avg.z /= n;

        for (auto c : pts) {
            c = c - avg;
            cout << setprecision(20) << fixed << c.x << " " << c.y << " " << c.z << "\n";
        }
        break;
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
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.21126761838571643079 -0.24668033012071098367 -0.18462825239648039468
0.30040028836334361465 -0.06757935864321174631 0.19525320808034630555
0.12289661901362098565 0.26103201146605989479 -0.14386315353894512178
-0.21202928899124816951 0.05322767729786283513 0.13323819785507921078

result:

ok OK. Max delta: 0.096440

Test #2:

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

input:

1
0.000000

output:

0.00000000000000000000 0.00000000000000000000 0.00000000000000000000

result:

ok OK. Max delta: 0.000000

Test #3:

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

input:

2
0.000000 0.938096
0.938096 0.000000

output:

-0.35517639295870998551 -0.14775305103008373811 0.26837435067483907862
0.35517639295870998551 0.14775305103008373811 -0.26837435067483907868

result:

ok OK. Max delta: 0.000000

Test #4:

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

input:

3
0.000000 0.769195 0.308169
0.769195 0.000000 0.686850
0.308169 0.686850 0.000000

output:

0.27119450154639531531 -0.10938343026065024577 0.07415756027527877953
-0.40259300364111007909 0.08156931876118116572 0.14297382416415282494
0.13139850209471476373 0.02781411149946908003 -0.21713138443943160449

result:

ok OK. Max delta: 0.065499

Test #5:

score: 0
Accepted
time: 0ms
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.02107812003268856357 -0.23632320060514163643 0.27124939624073550763
0.24308721899795243322 0.05047953325190399196 -0.05927350693317874245
0.12214881803884560333 0.05648195941027571085 0.14264960167579622546
-0.16603897514988848320 -0.42422240519198750619 0.12933958906002905522
-0.1781189418542209...

result:

ok OK. Max delta: 0.094386

Test #6:

score: 0
Accepted
time: 1ms
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.07611094945340264953 -0.56506879778267305624 0.00898709626233315810
-0.45697377386516848503 0.23965624006878236875 0.36378990461425489010
-0.12746254045813023100 0.16235199082715613133 0.14965929986450246411
0.21859893006593720518 0.09670202464272677936 -0.57354243163802988117
0.44416992447470650...

result:

ok OK. Max delta: 0.098227

Test #7:

score: 0
Accepted
time: 1ms
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.36705444719796921724 0.13793903614067928821 0.14398058962402837110
-0.03779996358638968820 0.50207454153717302715 -0.18285620707426438687
0.04742658879053675001 -0.08585695618962943949 0.07482178110131979264
-0.24850511821585307143 -0.25495746114949181918 -0.34132561242467449736
-0.222343262142092...

result:

ok OK. Max delta: 0.099765

Test #8:

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

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.02356625537331869902 0.31917471214501465384 -0.20695456694404957250
0.11088896265454297840 -0.11113391269243923199 0.07672371291194869945
0.01093913067342079445 -0.50431049564127995006 0.20755430993955044025
-0.02055782141448536554 0.26108181282733711166 -0.09327060070367540023
-0.024018398486281...

result:

ok OK. Max delta: 0.097878

Test #9:

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

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.41316053967549293984 0.04031754339893239847 0.18096415337597600043
-0.14066311534566615393 -0.27999019913892627331 -0.45215725654912217052
-0.09547069298390835156 -0.03981619189565881089 0.18816684391694357372
0.05732753313986417435 -0.25918077860714344111 0.03776509923367037379
-0.015645715203589...

result:

ok OK. Max delta: 0.099508

Test #10:

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

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.34210156900188326925 0.23330099120059545137 0.51751661204675004956
0.10737317057748168122 -0.32101888231310154049 -0.30470999374912206787
-0.11254055969425943412 0.04526182848308471155 0.29966730274099133907
-0.20098106703564218694 -0.06544810346862677976 -0.48668970855755098418
0.186982071129478...

result:

ok OK. Max delta: 0.096722

Test #11:

score: 0
Accepted
time: 0ms
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.02034643106395315430 -0.12173515872935126419 0.23463247004707799177
-0.35239712348892386878 -0.11783143979931450388 -0.21622986979131841707
0.28689964937716614477 0.00003330387558297664 0.33680722902482993164
0.08902879725826535473 -0.05411181022428438670 -0.46379795921400445487
-0.00586431749869...

result:

ok OK. Max delta: 0.098777

Test #12:

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

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.27577981706892396908 -0.16702498601302091598 0.20277605454415494464
-0.20774779991558635063 -0.38750259775219361084 -0.01744730787357015277
-0.62246288606333283720 0.05930048803166623164 -0.23040681709668597410
-0.14084700651521285980 -0.03298448401498655221 -0.44158032435290848854
0.3472958388835...

result:

ok OK. Max delta: 0.099756

Test #13:

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

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.29544379105598429598 -0.50474093567428691048 0.20082764537560410457
0.34101151605641770098 -0.19233215100408415093 0.22973801005100370092
0.29349032058860071627 0.31468065177293534450 -0.04659154282439631844
0.18592973829174255131 -0.28511817156737898497 -0.39462054828278294414
-0.4756095482218014...

result:

ok OK. Max delta: 0.099028

Test #14:

score: 0
Accepted
time: 25ms
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.21840823025948368875 -0.10597794012929977867 -0.20828024699762060661
-0.19077999979225371873 -0.24764280104794303789 -0.41356208561433037391
-0.07228319426552676883 -0.66978299169420936720 0.04735291391169192866
-0.16876400684630345179 0.31744221411357191116 0.64886862412934458215
0.4690195452021...

result:

ok OK. Max delta: 0.099444

Test #15:

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

input:

10
0.000000 0.655953 0.416075 0.956128 0.351321 0.411663 0.904277 0.786858 0.961004 1.159073
0.655953 0.000000 0.398507 0.430374 0.378366 0.531641 0.789955 0.396050 0.368849 1.088933
0.416075 0.398507 0.000000 0.976294 0.461240 0.328488 0.979923 0.705916 0.884932 1.254989
0.956128 0.430374 0.976294 ...

output:

-0.30007473824725849323 0.04646004535186344431 0.47163829572563385084
0.09038230902024393826 0.20577950280993771438 0.08974553400512683132
-0.37719028536794795833 0.34078516749745139323 0.18305012278809553150
0.40287363281746386271 0.15472616334235234390 -0.18823684229582538681
-0.153873617106195878...

result:

ok OK. Max delta: 0.097029

Test #16:

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

input:

10
0.000000 0.672245 0.576475 0.810904 0.599396 0.493165 0.431514 0.511677 0.859634 0.881368
0.672245 0.000000 1.249406 1.027657 0.113558 0.392208 0.862698 0.329856 1.012059 1.039747
0.576475 1.249406 0.000000 0.869439 1.254676 1.087547 0.535956 1.182094 0.744887 0.645939
0.810904 1.027657 0.869439 ...

output:

0.01124475408997140406 0.33885769208809611474 0.04826186831000619707
-0.39963026781255688410 -0.02627496993258351409 0.40249926110104720201
0.19557422892901656959 0.32883911687634083894 -0.59873099539267403754
0.35325458483067650713 -0.38869024763173185615 -0.19817927448547457048
-0.4466597890457711...

result:

ok OK. Max delta: 0.099713

Test #17:

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

input:

10
0.000000 0.609276 0.612588 0.898616 0.668529 0.802163 0.126104 0.681054 0.761434 0.310892
0.609276 0.000000 0.922363 0.423227 0.591390 0.662160 0.751720 0.241917 0.563127 0.693959
0.612588 0.922363 0.000000 0.873479 0.681583 0.707351 0.595097 0.923846 0.768951 0.393683
0.898616 0.423227 0.873479 ...

output:

-0.07142751284437847732 -0.47216830835830451781 0.03780070922968332107
-0.01999387640348773709 0.04037713154417376678 -0.44628266926900576179
-0.45960873573070100442 -0.04273271957755318701 0.34157143418366540819
0.13794415234688316141 0.36147358751935233020 -0.16034678300200623844
0.170234043994708...

result:

ok OK. Max delta: 0.097608

Test #18:

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

input:

10
0.000000 0.542508 0.426558 0.741404 0.733105 0.586307 0.271270 0.847645 0.757695 0.830800
0.542508 0.000000 0.497136 1.012191 1.083431 0.944439 0.618287 0.696705 0.472089 0.354373
0.426558 0.497136 0.000000 0.973354 0.928175 0.884683 0.594828 0.699473 0.534409 0.737409
0.741404 1.012191 0.973354 ...

output:

-0.16783028147341842365 -0.17752101674345832755 -0.25609470430474157762
0.25864528382853196691 0.10248060183716994925 -0.39292264736983636346
0.34456667341273978817 -0.26329436685501684447 -0.18041545482174100524
-0.27452752324826621298 0.37893504893519145782 0.33120126393091275680
-0.30964501511799...

result:

ok OK. Max delta: 0.099459

Test #19:

score: -100
Time Limit Exceeded

input:

10
0.000000 1.061016 0.689894 0.927767 0.698893 0.765947 0.661068 0.306274 0.338125 0.696899
1.061016 0.000000 0.648243 1.014484 1.091752 0.749377 0.935557 1.183802 0.696073 0.582378
0.689894 0.648243 0.000000 0.480864 0.914770 0.542060 0.834022 0.683526 0.147432 0.385821
0.927767 1.014484 0.480864 ...

output:


result: