QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#872652 | #8614. 3D | ucup-team055# | WA | 1785ms | 4096kb | C++17 | 5.3kb | 2025-01-26 03:14:47 | 2025-01-26 03:14:47 |
Judging History
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