QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#699201 | #2950. Growing Some Oobleck | nickbelov# | AC ✓ | 37ms | 7192kb | C++20 | 4.0kb | 2024-11-02 05:04:45 | 2024-11-02 05:04:46 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
ostream_iterator<T> oit(const string &s = " "){ return ostream_iterator<T>(cout,s.c_str()); }
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
#define A(a) begin(a),end(a)
inline auto len = ranges::ssize;
struct chash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
typedef vector<ll> vll;
using pll = pair<ll,ll>;
using pii = pair<int,int>;
constexpr ld EPSILON = 0;
constexpr ll NN = 2e5, M = 1000000007, L = 20;
ll f1[NN], f2[NN];
ll inv(ll a, ll b=M) { return 1 < a ? b - inv(b % a, a) * b / a : 1; } // inv a mod b
ll choose(ll n, ll k) { return f1[n] * f2[k] % M * f2[n - k] % M; } // n choose k
int n;
struct Circle {
ld x, y, r, s;
};
vector<Circle> circs;
void del(int i) {
swap(circs[i], circs[n-1]);
--n;
circs.pop_back();
}
void expand(ld t) {
for (auto& c : circs) {
c.r += c.s * t;
}
}
void cascade(int i) {
ld sx = 0, sy = 0, sa = 0, ms = 0;
int cnt = 0;
auto& c = circs[i];
vector<int> marked;
for (int j : rep(n)) {
auto& c2 = circs[j];
if (hypotl(c.x-c2.x, c.y-c2.y) <= c.r + c2.r + EPSILON) {
cnt++;
sx += c2.x;
sy += c2.y;
sa = hypotl(sa, c2.r);
ms = max(ms, c2.s);
marked.push_back(j);
}
}
if (marked.size() <= 1) return;
c.x = sx / cnt;
c.y = sy / cnt;
c.r = sa;
c.s = ms;
reverse(A(marked));
for (int x : marked) {
if (x == i) continue;
if (i == n-1) {
i = x;
}
del(x);
}
cascade(i);
}
void mrg() {
int a, b;
ld t = INFINITY;
for (int i : rep(n)) {
for (int j : rep(i)) {
auto& c1 = circs[i], c2 = circs[j];
ld t1 = (hypotl(c1.x - c2.x, c1.y - c2.y) - c1.r - c2.r) / (c1.s + c2.s);
if (t1 < t) {
a = i; b = j;
t = t1;
}
}
}
expand(t);
auto& c1 = circs[a], c2 = circs[b];
c1.x = (c1.x + c2.x) / 2;
c1.y = (c1.y + c2.y) / 2;
c1.r = hypotl(c1.r, c2.r);
c1.s = max(c1.s, c2.s);
if (a == n-1) a = b;
del(b);
cascade(a);
}
void run()
{
cin >> n;
circs.resize(n);
for (auto& c : circs) {
cin >> c.x >> c.y >> c.r >> c.s;
}
while (circs.size() > 1) mrg();
cout << fixed << setprecision(12) << circs[0].x << " " << circs[0].y << endl;
cout << circs[0].r << endl;
}
int main()
{
//KING OF THE WORLD...... U.W.T.B
cin.tie(0);
ios_base::sync_with_stdio(false);
f1[0] = 1;
f2[0] = 1;
for (int i = 1; i < NN; i++) {
f1[i] = f1[i - 1] * i % M;
f2[i] = inv(f1[i], M);
}
int t=1; while(t--) run();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 30ms
memory: 7052kb
input:
3 10 10 5 1 24 10 7 1 16 2 2 1
output:
16.500000000000 6.000000000000 10.440306508911
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 26ms
memory: 7132kb
input:
5 -5 0 1 1 6 0 1 1 0 7 1 1 0 -8 1 1 0 0 1 2
output:
1.187500000000 -3.125000000000 7.616776813122
result:
ok 3 numbers
Test #3:
score: 0
Accepted
time: 26ms
memory: 7048kb
input:
2 -1000000000 0 1 1 1000000000 0 1 1
output:
0.000000000000 0.000000000000 1414213562.373095048824
result:
ok 3 numbers
Test #4:
score: 0
Accepted
time: 29ms
memory: 7120kb
input:
4 -100000000 -1000000000 1 2 1000000000 -1000000000 1 2 -1000000000 1000000000 1 3 1000000000 1000000000 1 3
output:
225000000.000000000000 0.000000000000 1673350486.960810329299
result:
ok 3 numbers
Test #5:
score: 0
Accepted
time: 30ms
memory: 7100kb
input:
4 -100000000 -1000000000 1 1000000 1000000000 -1000000000 1 1000000 -1000000000 1000000000 1 3 1000000000 1000000000 1 3
output:
-137500000.000000000000 500000000.000000000000 2074241311.012399946107
result:
ok 3 numbers
Test #6:
score: 0
Accepted
time: 25ms
memory: 7068kb
input:
10 -1 1 1 1 3 1 1 1 8 1 1 1 21 1 1 1 55 1 1 1 155 1 1 1 355 1 1 1 900 1 1 1 2000 1 1 1 20000 1 1 1
output:
10640.589843750000 1.000000000000 13239.142792141766
result:
ok 3 numbers
Test #7:
score: 0
Accepted
time: 30ms
memory: 7180kb
input:
10 1 1 1 1 1 -3 1 1 1 -8 1 1 1 -21 1 1 1 -55 1 1 1 -155 1 1 1 -355 1 1 1 -900 1 1 1 -2000 1 1 1 -20000 1 1
output:
1.000000000000 -10640.589843750000 13239.142792141766
result:
ok 3 numbers
Test #8:
score: 0
Accepted
time: 26ms
memory: 7192kb
input:
8 -1 1 1 2 -5 5 1 2 0 6 1 1 -6 0 1 1 1001 -1 1 3 1005 -5 1 3 1006 0 1 1 1000 -6 1 1
output:
500.000000000000 0.000000000000 725.258698493373
result:
ok 3 numbers
Test #9:
score: 0
Accepted
time: 29ms
memory: 7056kb
input:
4 0 1 2 3 7 1 3 1 17 1 1 1 17 10 1 1
output:
13.625000000000 5.500000000000 11.229147340738
result:
ok 3 numbers
Test #10:
score: 0
Accepted
time: 30ms
memory: 7108kb
input:
4 0 1 2 1 7 1 3 3 17 1 1 1 17 10 1 1
output:
13.625000000000 5.500000000000 11.245832561442
result:
ok 3 numbers
Test #11:
score: 0
Accepted
time: 26ms
memory: 7080kb
input:
100 0 0 1 1 0 10 1 1 0 20 1 1 0 30 1 1 0 40 1 1 0 50 1 1 0 60 1 1 0 70 1 1 0 80 1 1 0 90 1 1 0 100 1 1 0 110 1 1 0 120 1 1 0 130 1 1 0 140 1 1 0 150 1 1 0 160 1 1 0 170 1 1 0 180 1 1 0 190 1 1 0 200 1 1 0 210 1 1 0 220 1 1 0 230 1 1 0 240 1 1 0 250 1 1 0 260 1 1 0 270 1 1 0 280 1 1 0 290 1 1 0 300 1...
output:
0.000000000000 10.000000000000 25.648610872120
result:
ok 3 numbers
Test #12:
score: 0
Accepted
time: 30ms
memory: 7136kb
input:
100 0 0 1 1 0 10 1 1 0 20 1 1 0 30 1 1 0 40 1 1 0 50 1 1 0 60 1 1 0 70 1 1 0 80 1 1 0 90 1 1 0 100 1 1 0 110 1 1 0 120 1 1 0 130 1 1 0 140 1 1 0 150 1 1 0 160 1 1 0 170 1 1 0 180 1 1 0 190 1 1 0 200 1 1 0 210 1 1 0 220 1 1 0 230 1 1 0 240 1 1 0 250 1 1 0 260 1 1 0 270 1 1 0 280 1 1 0 290 1 1 0 300 1...
output:
50.000000000000 261.249085504811 375.568946911709
result:
ok 3 numbers
Test #13:
score: 0
Accepted
time: 37ms
memory: 7116kb
input:
100 0 0 1 1 10 20 1 1 20 80 1 1 30 180 1 1 40 320 1 1 50 500 1 1 60 720 1 1 70 980 1 1 80 1280 1 1 90 1620 1 1 100 2000 1 1 110 2420 1 1 120 2880 1 1 130 3380 1 1 140 3920 1 1 150 4500 1 1 160 5120 1 1 170 5780 1 1 180 6480 1 1 190 7220 1 1 200 8000 1 1 210 8820 1 1 220 9680 1 1 230 10580 1 1 240 11...
output:
681.153564453125 107695.578613281250 84684.981560490749
result:
ok 3 numbers
Test #14:
score: 0
Accepted
time: 30ms
memory: 7180kb
input:
3 -1000000000 0 1 100000 1000000000 0 1 100000 1000000000 1000000000 1000000 1
output:
0.000000000000 250000000.000000000000 1457737973.711369821685
result:
ok 3 numbers
Test #15:
score: 0
Accepted
time: 30ms
memory: 7096kb
input:
4 -1000000000 0 1 100000 1000000000 0 1 100000 1000000000 1000000000 1000000 1 0 0 2 2
output:
250000000.000000000000 250000000.000000000000 1414185636.997804428916
result:
ok 3 numbers
Test #16:
score: 0
Accepted
time: 36ms
memory: 7120kb
input:
100 -993853835 -889234028 372418 480830 967974474 863745382 845086 316834 902310614 -902493899 405732 380202 -37824102 -287741231 400050 942967 971969049 92047940 468507 921761 -600612683 -278056632 977642 172884 235442253 851973492 855665 943236 407860875 592755649 345538 823894 227087840 -93883735...
output:
712148141.458007684676 752427048.448427264055 940126064.811280636524
result:
ok 3 numbers
Test #17:
score: 0
Accepted
time: 34ms
memory: 7100kb
input:
100 -991006979 -78398598 888529 6397 -168191015 86162807 953291 446246 -941099384 195245041 482901 602525 843205725 396143650 458929 285642 -170766083 -799927656 886603 482177 -398289374 544239452 298537 456698 -873551763 873954869 686379 697063 -874344706 -15896687 396572 296644 151301482 -63675804...
output:
371827339.397315629321 266951144.242265496432 1209296596.114549955353
result:
ok 3 numbers
Test #18:
score: 0
Accepted
time: 37ms
memory: 7084kb
input:
100 -174958760 -871174978 565937 356774 -925634674 -432225577 701564 37257 -22555735 211243118 48552 255475 714731061 136239021 326781 837955 -932589505 37077711 508137 17719 -979235051 376608958 350534 645908 288796461 -543046646 582992 37683 172529142 294162972 97262 459348 -615050639 378778468 44...
output:
198360260.461106631497 170910810.394741422599 1440508744.012454642216
result:
ok 3 numbers
Test #19:
score: 0
Accepted
time: 37ms
memory: 7104kb
input:
100 641089458 483532290 243344 707151 464405314 -950613961 449837 114062 895987914 227241195 99998 394220 586256397 -123665608 708837 390270 453070722 874083079 615466 553261 587302921 208978464 888327 320914 -548855314 187435488 479604 864098 -780597010 604222630 797951 107848 766080888 -753168664 ...
output:
-131644699.449379433529 639893986.290879567503 1135881519.562323578633
result:
ok 3 numbers
Test #20:
score: 0
Accepted
time: 33ms
memory: 7128kb
input:
100 -690345971 -309244090 434956 543324 -293038345 678481303 198110 705072 -332952084 243239272 665648 47171 457781733 -383570237 576688 942583 -308752700 -436395201 237000 88803 6357244 41347970 940324 510123 760976558 917917621 862012 204718 413760485 914282289 498641 756346 -271233 262367852 4759...
output:
231242612.122212473536 -300376760.267043219676 1068567816.808067150065
result:
ok 3 numbers
Test #21:
score: 0
Accepted
time: 34ms
memory: 7040kb
input:
100 791419962 -705632280 273660 718513 -671760175 419287111 72247 757679 -947422084 -822503513 691371 616543 -680197423 560219273 767716 218740 -689664411 -17892517 547767 113677 789626230 -968725453 723426 604728 342150670 209416864 310319 617925 -62802591 -4429706 848985 580596 690294531 -30360571...
output:
372796359.896457460185 -441709616.794075895246 1155102638.884534906596
result:
ok 3 numbers
Test #22:
score: 0
Accepted
time: 34ms
memory: 7036kb
input:
100 -540015467 649074988 951067 68891 718279814 -99101273 820519 348689 -28878435 -806505436 742818 269493 -808672087 300314644 635568 285258 695995816 819112850 169301 649218 208680553 863644053 261219 793938 -495501106 939898998 206931 444340 -868445095 305629953 549675 743300 -76057590 711930803 ...
output:
-579117325.746015628160 -700064522.099570274353 1179476387.716503174044
result:
ok 3 numbers
Test #23:
score: 0
Accepted
time: 34ms
memory: 7068kb
input:
100 941750466 252686798 789771 244079 339557984 -358295465 694656 887091 -643348434 275235426 282746 838866 200832405 -903379495 826596 561415 315084105 -909868114 965863 674091 991949539 -293913017 44321 888543 -914326993 231398240 655237 371752 654991829 -613082042 900020 567550 614508174 14595723...
output:
435381577.186847953650 349150452.246003829874 1522214340.971888387110
result:
ok 3 numbers
Test #24:
score: 0
Accepted
time: 29ms
memory: 7184kb
input:
2 1 1 1 1 5 1 1 1
output:
3.000000000000 1.000000000000 2.828427124746
result:
ok 3 numbers
Test #25:
score: 0
Accepted
time: 25ms
memory: 7096kb
input:
5 3 4 5 1 17 4 7 1 10 -13 6 2 10 21 7 1 -7 4 1 1
output:
1.500000000000 4.000000000000 15.231546211728
result:
ok 3 numbers