QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#871451#8614. 3Ducup-team6275#TL 7ms4096kbC++233.6kb2025-01-25 20:45:362025-01-25 20:46:10

Judging History

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

  • [2025-01-25 20:46:10]
  • 评测
  • 测评结果:TL
  • 用时:7ms
  • 内存:4096kb
  • [2025-01-25 20:45:36]
  • 提交

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(234);
mt19937 rndint(234);
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;

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

    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() + 0.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]), ypp = pts[i] - (pts[v] - pts[i]).norm(d[v][i]);
                if (dist(yp, pts[v]) > dist(ypp, pts[v]))
                    yp = ypp;

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

            ++iters;
            if (iters >= 5000) {
                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.77397553398667076076 0.72380468864136182584 1.87926170747147707840
0.16904871603044445321 1.10282467439847048287 1.88606643004627473528
0.30957787837398679820 0.54133937447621975538 1.73379825737681966986
0.58257743997664281896 1.04235557921123660999 1.78281410323920337820

result:

ok OK. Max delta: 0.081890

Test #2:

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

input:

1
0.000000

output:

0.66869392477264066871 1.24617007957988924619 1.64946299193055564947

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:

1.19188022685328850960 2.13605481483689965509 0.39721014426560226311
0.70439711027596847693 1.34885643646776585513 0.24653489957999020184

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.61989656919177479107 0.49131880904189847585 1.00072237715968162303
0.81225034710557382348 0.35808234299362195046 0.27205951432606064524
0.99946065381680866273 0.42501788611627389704 0.91845747260012845087

result:

ok OK. Max delta: 0.085826

Test #5:

score: 0
Accepted
time: 1ms
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:

1.77384376345180201976 0.72835936054981032222 0.79599067735180597508
1.33822475945657744473 0.94454592039144733917 0.89368705371397199277
1.39597964977337041389 0.76333259077971407679 0.81708509476954962298
1.77895331555413767995 0.57544244222429050015 0.52852891826615186287
0.95806066322616643477 1...

result:

ok OK. Max delta: 0.098593

Test #6:

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

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.31646386563580787557 1.05879760154928637670 1.33314768209895826313
0.48152292374406754639 0.28059099666356405518 0.78739551561114407008
0.80603813431370398485 0.46685338906721824683 1.09600774672013729933
1.31039351315746726515 1.04853977479266395221 1.24952616061030254819
1.00944715053039424510 1...

result:

ok OK. Max delta: 0.099272

Test #7:

score: 0
Accepted
time: 0ms
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:

1.28834149803035963181 0.75059479860962955930 0.67989050997320145538
0.80508875551358215802 1.14386937711231968350 1.01559144460241094099
1.38403451919707193838 1.15451623285110588791 0.73984870806818018533
1.56857203664318184573 1.34683161345129844000 1.17583496430461227795
1.62248746896881318382 1...

result:

ok OK. Max delta: 0.098171

Test #8:

score: 0
Accepted
time: 1ms
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.55856209908605820738 0.43011393485586199657 0.81339337848004970193
0.86768455725238446589 0.73680304478476510086 0.80306122152452906460
1.25514985847979465181 0.87730669312967767237 0.70577268313044480683
0.55348338628224274318 0.54589786792365596521 0.79122570299256152578
0.97521377054851963106 0...

result:

ok OK. Max delta: 0.099521

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:

1.12214326240141983320 0.72490953800467415819 1.18817815461982192982
0.48139961320298446122 1.36024014078888501409 1.11887034132703356974
1.11726675353673169972 1.21345842559561867681 1.07225264539180324122
0.91430532272700254260 1.07984657604351825296 0.91473704504972052807
0.67301511143719357715 1...

result:

ok OK. Max delta: 0.099951

Test #10:

score: 0
Accepted
time: 4ms
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:

1.09232053869773680730 0.28889907783756929815 0.78982009219587699726
0.88721639473742020475 -0.73729858520723372777 0.41515405045123443897
0.88527643137580933682 -0.02710484868044272618 0.70938470935158343361
1.30805645853550900923 -0.54669433732922227047 0.27837906093853050478
0.7338205652073994299...

result:

ok OK. Max delta: 0.099965

Test #11:

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

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:

1.33305369172020082077 1.33390754960647932130 0.90107477856022272455
1.40554470493694425601 0.84913174878097446679 1.19124860773837576693
1.06040951357471627378 1.55486334862379976644 0.83769827089824876545
0.86339324625672770881 0.83061222906602287167 1.15274045130959402789
0.95364614272115199884 1...

result:

ok OK. Max delta: 0.099281

Test #12:

score: 0
Accepted
time: 3ms
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:

1.73530118294719562521 1.57275595820508526639 1.28892659552640757902
1.77265311573620221468 1.01547981147232036143 1.45166593497825453514
1.34529082660166033529 0.73704100232385429164 1.66871843748113569798
1.15885164508878432178 1.03420772796082415901 1.46135713172186262583
1.55428597825277399523 1...

result:

ok OK. Max delta: 0.099450

Test #13:

score: 0
Accepted
time: 1ms
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.62297356182787319632 1.48463676257944428467 1.14526100054767128141
0.90928659566559132685 1.49200670976018502786 1.00564463747867311003
1.25516363809704295496 1.29938309413758750778 0.60652446721628733533
0.56927196710330300449 1.10344682005891677888 0.61109829679940322241
1.23405377378551007746 0...

result:

ok OK. Max delta: 0.099538

Test #14:

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

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:

1.03847893850741114280 0.98512974438570594939 1.33103750790378549300
1.21753753728086979422 0.85292331046308285608 1.45946468143324939730
1.53268597368091148074 1.25897462144057545417 1.15414245589457293347
0.52864160083278263519 1.28314299421506777365 0.54584807299425866847
0.96073567266475175865 0...

result:

ok OK. Max delta: 0.099750

Test #15:

score: 0
Accepted
time: 0ms
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:

1.44948636367616287405 1.47689891742186023694 1.22894961323969657808
1.19805111101198614933 0.99104136631881711091 0.94055653206045135328
1.46048266002799371902 1.34900615267654907874 0.82550622226693206392
0.95373628284744140643 0.71844975227196714431 1.24034221318692411797
1.15131985421229732247 1...

result:

ok OK. Max delta: 0.099491

Test #16:

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

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:

1.44326864615175721909 1.41138425815912693293 1.26206409572032219137
1.54150451963379853614 0.99275765159037573644 1.73433200481726621260
1.16543187629122446550 1.46290791359805940133 0.64829531738456995700
0.83535830128472533481 0.83486971245836949908 1.07807817561447190401
1.40645707436374519522 0...

result:

ok OK. Max delta: 0.099217

Test #17:

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

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:

1.01623296493780983338 1.44246262816806261413 1.41292375973947132990
1.34767467825915613841 0.87814870131831000927 1.56274486963428614237
1.32279596456847972727 1.52568394477920037762 0.87042779987169546329
1.27260239915691091483 0.64596801687312805756 1.12794477150239423255
1.21430535970297306773 0...

result:

ok OK. Max delta: 0.096238

Test #18:

score: -100
Time Limit Exceeded

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:


result: