QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#56065 | #4880. Network Transfer | triple__a# | AC ✓ | 345ms | 33468kb | C++ | 12.1kb | 2022-10-16 19:31:02 | 2022-10-16 19:31:03 |
Judging History
answer
// #pragma comment(linker, "/STACK:102400000,102400000")
#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
// #pragma GCC optimize("trapv")
#include<bits/stdc++.h>
// #include <bits/extc++.h>
#define int long long
#define double long double
// #define i128 long long
// #define double long double
using namespace std;
#define rep(i,n) for (int i=0;i<(int)(n);++i)
#define rep1(i,n) for (int i=1;i<=(int)(n);++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second
typedef long long ll;
typedef unsigned long long ull;
// typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
namespace internal {
// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
// constexpr int bsf_constexpr(unsigned int n) {
// int x = 0;
// while (!(n & (1 << x))) x++;
// return x;
// }
// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
} // namespace internal
template <class S,
S (*op)(S, S),
S (*e)(),
class F,
S (*mapping)(F, S),
F (*composition)(F, F),
F (*id)()>
struct lazy_segtree {
public:
lazy_segtree() : lazy_segtree(0) {}
explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
explicit lazy_segtree(const std::vector<S>& v) : _n((int)(v.size())) {
log = internal::ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
struct SplayTree {
struct Node {
int ch[2] = {0, 0}, p = 0;
long long self = 0, path = 0; // Path aggregates
long long sub = 0, vir = 0; // Subtree aggregates
bool flip = 0; // Lazy tags
};
vector<Node> T;
SplayTree(int n) : T(n + 1) {}
void push(int x) {
if (!x || !T[x].flip) return;
int l = T[x].ch[0], r = T[x].ch[1];
T[l].flip ^= 1, T[r].flip ^= 1;
swap(T[x].ch[0], T[x].ch[1]);
T[x].flip = 0;
}
void pull(int x) {
int l = T[x].ch[0], r = T[x].ch[1]; push(l); push(r);
T[x].path = T[l].path + T[x].self + T[r].path;
T[x].sub = T[x].vir + T[l].sub + T[r].sub + T[x].self;
}
void set(int x, int d, int y) {
T[x].ch[d] = y; T[y].p = x; pull(x);
}
void splay(int x) {
auto dir = [&](int x) {
int p = T[x].p; if (!p) return -1;
return T[p].ch[0] == x ? 0 : T[p].ch[1] == x ? 1 : -1;
};
auto rotate = [&](int x) {
int y = T[x].p, z = T[y].p, dx = dir(x), dy = dir(y);
set(y, dx, T[x].ch[!dx]);
set(x, !dx, y);
if (~dy) set(z, dy, x);
T[x].p = z;
};
for (push(x); ~dir(x); ) {
int y = T[x].p, z = T[y].p;
push(z); push(y); push(x);
int dx = dir(x), dy = dir(y);
if (~dy) rotate(dx != dy ? x : y);
rotate(x);
}
}
};
struct LinkCut : SplayTree {
LinkCut(int n) : SplayTree(n) {}
int access(int x) {
int u = x, v = 0;
for (; u; v = u, u = T[u].p) {
splay(u);
int& ov = T[u].ch[1];
T[u].vir += T[ov].sub;
T[u].vir -= T[v].sub;
ov = v; pull(u);
}
return splay(x), v;
}
void reroot(int x) {
access(x); T[x].flip ^= 1; push(x);
}
void Link(int u, int v) {
reroot(u); access(v);
T[v].vir += T[u].sub;
T[u].p = v; pull(v);
}
void Cut(int u, int v) {
reroot(u); access(v);
T[v].ch[0] = T[u].p = 0; pull(v);
}
// Rooted tree LCA. Returns 0 if u and v arent connected.
int LCA(int u, int v) {
if (u == v) return u;
access(u); int ret = access(v);
return T[u].p ? ret : 0;
}
// Query subtree of u where v is outside the subtree.
long long Subtree(int u, int v) {
reroot(v); access(u); return T[u].vir + T[u].self;
}
// Query path [u..v]
long long Path(int u, int v) {
reroot(u); access(v); return T[v].path;
}
// Update vertex u with value v
void Update(int u, long long v) {
access(u); T[u].self = v; pull(u);
}
};
bool dfs(int a, int L, vector<vi>& g, vi& btoa, vi& A, vi& B) {
if (A[a] != L) return 0;
A[a] = -1;
for (int b : g[a]) if (B[b] == L + 1) {
B[b] = 0;
if (btoa[b] == -1 || dfs(btoa[b], L + 1, g, btoa, A, B))
return btoa[b] = a, 1;
}
return 0;
}
int hopcroftKarp(vector<vi>& g, vi& btoa) {
int res = 0;
vi A(g.size()), B(btoa.size()), cur, next;
for (;;) {
fill(range(A), 0);
fill(range(B), 0);
/// Find the starting nodes for BFS (i.e. layer 0).
cur.clear();
for (int a : btoa) if(a != -1) A[a] = -1;
rep(a,sz(g)) if(A[a] == 0) cur.push_back(a);
/// Find all layers using bfs.
for (int lay = 1;; lay++) {
bool islast = 0;
next.clear();
for (int a : cur) for (int b : g[a]) {
if (btoa[b] == -1) {
B[b] = lay;
islast = 1;
}
else if (btoa[b] != a && !B[b]) {
B[b] = lay;
next.push_back(btoa[b]);
}
}
if (islast) break;
if (next.empty()) return res;
for (int a : next) A[a] = lay;
cur.swap(next);
}
/// Use DFS to scan for augmenting paths.
rep(a,sz(g))
res += dfs(a, 0, g, btoa, A, B);
}
}
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
const int mod=998244353;
const int base[]={12321,32123};
const double EPS=1e-9;
const double pi=acos(-1);
const int INF=1e18;
const int N=300007;
mt19937 rng(1235);
int modpow(int u,int v){
int ans=1, t=u;
while (v){
if (v&1) ans=ans*t%mod;
t=t*t%mod, v>>=1;
}
return ans;
}
// tuple<int,vi,vector<vi>> gauss(vector<vi> a)//sum = a[i][m]
// {
// int n=a.size(),m=a[0].size()-1,i,j,k,l,R=m;
// vi fix(m,-1);
// for (i=l=0;i<m;i++)
// {
// for (j=l;j<n;j++) if (a[j][i]) break;
// if (j==n) continue;
// fix[i]=l;--R;
// swap(a[l],a[j]);
// int x=modpow(a[l][i],mod-2);
// for (k=i;k<=m;k++) a[l][k]=(ll)a[l][k]*x%mod;
// for (auto &v:a) if (v.data()!=a[l].data())
// {
// x=mod-v[i];
// for (k=m;k>=i;k--) v[k]=(v[k]+(ll)x*a[l][k])%mod;
// }
// ++l;
// }
// for (i=l;i<n;i++) if (a[i][m]) return {-1,{},{}};
// vi r(m);
// vector<vi> c;
// for (i=0;i<m;i++) if (fix[i]!=-1) r[i]=a[fix[i]][m];
// for (i=0;i<m;i++) if (fix[i]==-1)
// {
// vi r(m);
// r[i]=1;
// for (j=0;j<m;j++) if (fix[j]!=-1) r[j]=(mod-a[fix[j]][i])%mod;
// c.push_back(r);
// }
// return {R,r,c};
// }
struct info{
int t,s,p,id;
friend bool operator<(info &l,info &r){
return l.t<r.t;
}
};
vector<info> a;
int p[N];
double ans[N];
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cout.precision(15);
int n,w;
cin>>n>>w;
rep(i,n){
int u,v,w;
cin>>u>>v>>w;
p[i+1]=w;
a.pb((info){u,v,w,i+1});
}
a.pb((info){INF,INF,0,0});
sort(range(a));
int sum=0;
double time_el=0;
double prv=0;
set<pair<double,int>> pq;
for (auto c:a){
while (sz(pq)){
auto ret=*pq.begin();
if (ret.first>time_el+1.0*(c.t-prv)/sum) break;
prv+=(ret.first-time_el)*sum, time_el=ret.first; sum-=p[ret.second];
ans[ret.second]=prv;
pq.erase(ret);
}
if (sum) time_el+=1.0*(c.t-prv)/sum;
prv=c.t;
// cerr<<time_el<<" "<<1.0*c.s/c.p/w+time_el<<endl;
if (c.p) pq.insert({1.0*c.s/c.p/w+time_el,c.id});
sum+=c.p;
}
rep1(i,n) cout<<ans[i]<<"\n";
return 0;
}
/*
3
2
1 2
5
5 2 4 3 1
10
3 8 8 2 9 1 6 2 8 3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5808kb
input:
2 10 0 100 2 4 200 1
output:
13 30
result:
ok 2 numbers
Test #2:
score: 0
Accepted
time: 2ms
memory: 5752kb
input:
2 10 30 200 1 10 100 2
output:
50 20
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 5752kb
input:
1 10000000 0 1 42
output:
1e-07
result:
ok found '0.0000001', expected '0.0000001', error '0.0000000'
Test #4:
score: 0
Accepted
time: 3ms
memory: 5868kb
input:
1 10000000 42 1 42
output:
42.0000001
result:
ok found '42.0000001', expected '42.0000001', error '0.0000000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 5916kb
input:
1 10000000 42 10000000 42
output:
43
result:
ok found '43.0000000', expected '43.0000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 5752kb
input:
1 10000000 10000000 1 1
output:
10000000.0000001
result:
ok found '10000000.0000001', expected '10000000.0000001', error '0.0000000'
Test #7:
score: 0
Accepted
time: 2ms
memory: 5816kb
input:
1 10000000 1 1 100
output:
1.0000001
result:
ok found '1.0000001', expected '1.0000001', error '0.0000000'
Test #8:
score: 0
Accepted
time: 2ms
memory: 5828kb
input:
1 1 10000000 10000000 100
output:
20000000
result:
ok found '20000000.0000000', expected '20000000.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 197ms
memory: 31820kb
input:
200000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10000000 1 10000000 10...
output:
2000010000000 2000010000000 2000010000000 2000010000000 2000010000000 2000010000000 2000010000000 2000010000000 2000010000000 2000010000000 2000010000000 2000010000000 2000010000000 2000010000000 2000010000000 2000010000000 2000010000000 2000010000000 2000010000000 2000010000000 2000010000000 200001...
result:
ok 200000 numbers
Test #10:
score: 0
Accepted
time: 278ms
memory: 32180kb
input:
200000 1 10000000 10000000 22 10000000 10000000 62 10000000 10000000 71 10000000 10000000 73 10000000 10000000 82 10000000 10000000 15 10000000 10000000 60 10000000 10000000 26 10000000 10000000 35 10000000 10000000 83 10000000 10000000 58 10000000 10000000 84 10000000 10000000 23 10000000 10000000 ...
output:
1790041363636.36 1390577580645.16 1300784647887.32 1280812465753.42 1190840487804.88 1859583333333.33 1410498166666.67 1750241923076.92 1660420857142.86 1180833975903.61 1430416379310.34 1170834642857.14 1780072608695.65 1610417250000 1250849473684.21 1660420857142.86 1540342978723.4 1500271176470.5...
result:
ok 200000 numbers
Test #11:
score: 0
Accepted
time: 344ms
memory: 33020kb
input:
199293 5 9504657 9159218 4 9229606 9939393 93 9949326 9400061 74 9049202 9678955 63 9856746 9805686 100 9900514 9492706 58 9077984 9828311 42 9082259 9783365 78 9815702 9654015 95 9655893 9753916 11 9027905 9930425 9 9210664 9496857 85 9488366 9132506 56 9416678 9238290 2 9475297 9343399 28 9442121 ...
output:
372606864555.123 212211534775.653 238948149663.04 263425611185.353 197063144013.495 270580494646.032 303467045798.255 237141228118.924 203504180187.051 360171498662.945 364170179095.572 219530866865.628 270186214835.578 376567304898.911 326396146375.99 351352560113.336 354448144301.524 336618594785....
result:
ok 199293 numbers
Test #12:
score: 0
Accepted
time: 315ms
memory: 32740kb
input:
199775 5 9573917 9665464 57 9498813 9469832 81 9885957 9606395 14 9397765 9003071 9 9246019 9070405 26 9740136 9081183 11 9893308 9667485 60 9912483 9414387 94 9934996 9683245 7 9359993 9793294 90 9852046 9209808 22 9704268 9048813 52 9066664 9842295 49 9894656 9914370 56 9520915 9685732 36 9507809 ...
output:
275136188681.623 227063705577.187 355194309827.037 363385338618.769 329856159627.166 359600267866.413 269538859112.944 201263971424.147 368365549271.434 215596647879.434 338462086635.512 277864582191.777 291752383805.083 279643237081.527 314523554485.674 240471104814.772 368753312757.427 27485801021...
result:
ok 199775 numbers
Test #13:
score: 0
Accepted
time: 310ms
memory: 32256kb
input:
199876 10 9569180 9097026 11 9805018 9888590 69 9859588 9812730 54 9708644 9290190 38 9672977 9335125 45 9617443 9706660 56 9670948 9431976 69 9705708 9008410 2 9091288 9600793 23 9064094 9794988 56 9750869 9563190 30 9234184 9600771 22 9681961 9478086 50 9410316 9590449 15 9604218 9991066 51 957349...
output:
179887507879.351 127724903099.116 141024141836.351 153787858998.035 147195733048.118 138618997279.591 124676275642.348 188810825750.261 169163511122.132 139088289036.244 162417585447.203 170108072542.117 143081618014.832 176681729512.214 144626707369.681 152539684945.413 99669425946.5458 18708905846...
result:
ok 199876 numbers
Test #14:
score: 0
Accepted
time: 334ms
memory: 32120kb
input:
199977 4 9602127 9565587 73 9111223 9419029 57 9833218 9019063 97 9020206 9577308 79 9062250 9637529 67 9457065 9295138 1 9448587 9234150 78 9535931 9639433 15 9247581 9592339 40 9768195 9797367 34 9649692 9879574 35 9727787 9190412 97 9260259 9150191 43 9851295 9229529 69 9724520 9333397 67 9676184...
output:
304491753262.739 340031067721.019 234313922207.067 290561445183.444 319806025765.541 474840344781.47 286089986044.73 441518236521.844 382411279202.561 398221219099.161 396587568673.449 238678764660.485 370475863738.505 307996730448.384 314703553472.792 237454044388.288 292588539076.149 384561055908....
result:
ok 199977 numbers
Test #15:
score: 0
Accepted
time: 340ms
memory: 32580kb
input:
199077 6 9634388 9960151 22 9418114 9874787 41 9769850 9225397 37 9368769 9901425 8 9489208 9902249 82 9371370 9920615 49 9263226 9036325 88 9329155 9233456 23 9366876 9584570 56 9434611 9799061 9 9473832 9195956 44 9220704 9779369 72 9801558 9822981 43 9366955 9830926 27 9770139 9638731 78 9741872 ...
output:
283688147387.333 254552170732.088 256675980123.554 304680729443.034 192633843521.356 242706661004.994 170818527368.701 279445737169.918 229155389462.985 303032608931.143 245028698316.45 206387719766.668 251159922565.221 275605305983.79 195456302719.261 207311425588.767 208431744492.26 200745983734.1...
result:
ok 199077 numbers
Test #16:
score: 0
Accepted
time: 242ms
memory: 16976kb
input:
199174 94 4939842 606 76 1166421 867 100 9051103 784 55 8172658 675 51 3743680 551 61 2613139 796 25 6619357 995 81 4244151 919 13 1565998 618 89 8971567 956 48 4453079 696 6 6507538 985 84 821657 762 98 5429287 786 27 6562208 661 86 286640 615 36 6512669 689 74 219589 615 49 8412173 719 58 8817089 ...
output:
4939848.44680851 1166430.22340426 9051111.34042553 8172665.18085106 3743685.86170213 2613147.46808511 6619367.58510638 4244160.77659574 1566004.57446809 8971577.17021277 4453091.60638298 6507551.14994934 821665.106382979 5429295.39361702 6562215.03191489 286647.393617021 6512680.57921219 219602.0851...
result:
ok 199174 numbers
Test #17:
score: 0
Accepted
time: 228ms
memory: 16532kb
input:
199275 58 420812 937 34 5358924 565 84 341963 608 95 9557118 546 80 3131446 587 87 4631085 759 74 1944615 555 90 9739783 504 22 6129096 823 9 9113009 779 15 5896446 737 11 2838089 778 63 2887413 545 3 9842144 566 82 4824038 515 2 3489410 943 99 4094375 674 67 5967153 825 83 8442695 661 5 1099067 961...
output:
420828.155172414 5358933.74137931 341973.703448276 9557130.93403941 3131456.12068966 4631098.0862069 1944624.56896552 9739791.68965517 6129110.73754789 9113022.43103448 5896464.60344828 2838116.85618928 2887427.4137931 9842153.75862069 4824046.87931034 3489426.25862069 4094386.62068966 5967167.22413...
result:
ok 199275 numbers
Test #18:
score: 0
Accepted
time: 216ms
memory: 16444kb
input:
199757 100 8599274 773 87 2248916 983 76 6665957 948 34 8244088 933 17 4788589 623 6 4017807 722 19 4934229 616 11 202280 590 38 692193 527 18 9188184 884 97 2306679 771 19 9102374 572 34 2551259 547 96 6886224 621 32 3085867 871 17 6758447 763 57 1742348 667 52 4050359 520 18 808859 610 60 8347912 ...
output:
8599282.52712644 2248929.21855263 6665969.22 8244097.33 4788595.23 4017814.22 4934235.16 202285.9 692198.27 9188192.84 2306686.71 9102379.72 2551264.499375 6886230.538125 3085875.71 6758458.78263158 1742354.67 4050364.2 808865.1 8347917.09 9544828.7421875 8902042.01 4913605.65 9586502.44 9778905.2 5...
result:
ok 199757 numbers
Test #19:
score: 0
Accepted
time: 334ms
memory: 30616kb
input:
199301 55 9625480 9580 55 1972191 9544 50 2023060 7409 51 3155002 5100 49 5157066 8962 57 8573320 9043 52 5593516 7630 69 4095980 7228 37 9700572 7655 95 4873927 6900 49 8970656 7567 35 4513218 7294 83 90439 8204 19 2350487 9774 100 8833379 7311 70 8720440 6645 16 5196961 9762 63 7589832 6318 17 504...
output:
22664764.1775698 19072434.5275945 14847167.731288 13479463.3024839 20842918.8926182 22479839.0094956 18374375.9549873 21677924.3523049 18966017.791127 19820640.7005919 23346119.1813412 14514855.7235717 20704922.9341262 9826141.15949291 20068809.8719482 25071221.6776228 20766430.7203607 24773065.8199...
result:
ok 199301 numbers
Test #20:
score: 0
Accepted
time: 302ms
memory: 28184kb
input:
199784 70 5106450 7012 8 8862184 6409 38 3313920 6644 90 1841972 6860 90 9511699 8604 83 5624399 9771 93 3616263 6180 86 6894122 9030 49 4263669 9105 11 4949103 5598 32 5380890 6955 48 8146280 6286 53 7123063 6952 11 9394568 8476 55 4759565 6568 78 6956343 7496 74 7811801 9766 52 5673038 8211 55 507...
output:
20569989.7938128 17924700.661383 6678833.93628122 3781477.14365081 16565452.197705 13829173.0919485 7161775.57489918 17739360.8462976 20493408.0622397 16664943.1772303 15857800.2081597 16526407.0936968 20285025.5989921 17776581.9574014 10634690.714593 15012054.6006869 18022459.2751649 16268971.79811...
result:
ok 199784 numbers
Test #21:
score: 0
Accepted
time: 329ms
memory: 26000kb
input:
199504 87 3284911 7920 70 8087820 7643 26 4604781 8931 34 5562076 8619 20 6201975 6720 98 9977988 8972 46 6605878 7152 95 2389753 7357 65 8826767 9661 24 5090545 8402 2 1791123 7868 49 9443698 5279 28 4155685 8121 8 3807424 7178 9 3021395 9299 93 225379 7716 41 5459773 5824 41 1420601 8155 89 744193...
output:
6416886.86267407 15527062.0569984 14488552.389328 15826799.68859 9289865.23356399 15136631.6552396 10288299.8330796 4661712.47131447 15976522.9439517 17111357.5411635 4630547.05903062 15007084.3592187 16615825.3177797 16415542.4827255 5457325.1437294 684855.404640713 12062718.4597116 2452961.1543129...
result:
ok 199504 numbers
Test #22:
score: 0
Accepted
time: 336ms
memory: 32236kb
input:
199447 66 1042403 67371 93 1128688 78245 76 5016768 50046 51 8688565 60236 62 7728578 73421 61 4914558 84844 51 4044583 90549 45 4037722 73419 85 533462 83816 56 832748 81898 38 2603184 60202 97 7543832 99993 32 8706211 91645 79 5544589 91922 58 8719389 94288 83 9443633 51194 58 710110 98781 29 9077...
output:
97353589.26238 134963509.310392 139517888.212164 141786058.523869 157334920.17192 175394851.272493 184140886.526916 126378138.861687 163471348.715229 184991893.117475 90962705.0566139 200054135.804035 155247504.722038 173087974.443246 153779101.543327 134152145.318263 201126873.6033 146215731.164282...
result:
ok 199447 numbers
Test #23:
score: 0
Accepted
time: 345ms
memory: 32836kb
input:
199929 82 9220865 86552 59 2985547 66016 60 1340761 51929 90 7375534 79510 99 4418854 68267 87 6932503 96935 100 7034197 65152 55 9533354 87179 1 5096560 88788 73 974191 95082 21 6677774 96696 10 1176893 73873 11 5738833 74842 80 9957447 62211 17 4645574 77470 94 7679536 61562 25 3324950 83656 14 98...
output:
137442730.623504 117719935.423043 60788949.550715 100808309.62369 95137085.2244394 113655203.673641 125979076.426221 182717780.304845 126235560.611792 167628018.3988 176362017.876936 172963004.019428 110101567.382926 164701871.194251 99290091.1363269 155451189.610926 171789653.370507 163509659.66922...
result:
ok 199929 numbers
Test #24:
score: 0
Accepted
time: 301ms
memory: 31808kb
input:
199029 73 4701835 79195 8 2211183 66584 48 2631622 53813 30 8759994 85987 36 8773487 81715 6 6319225 90424 41 23811 53497 64 2331496 50938 10 9659659 75158 89 6082500 89664 91 8121141 51790 18 2474312 52613 82 2771456 90383 69 7001526 77641 71 2907404 97855 14 948572 53328 84 3604146 68532 7 2907887...
output:
197343781.133927 146266455.203146 160277245.026007 172793852.192166 199572245.4456 169801859.050698 64949674.5064038 189590139.181984 118032789.573732 127144382.914736 178153214.122072 83736576.602192 143463781.904461 135320085.159299 193921930.410481 73566489.3723968 197237455.989795 146316945.4691...
result:
ok 199029 numbers
Test #25:
score: 0
Accepted
time: 322ms
memory: 33108kb
input:
199673 56 2610387 845669 2 1687829 988340 72 3821139 870884 35 2813428 799092 7 1365018 803557 95 9357496 513441 25 731413 980028 93 8363930 565303 23 4733785 973636 18 167256 773886 29 51133 651716 90 3480326 674090 12 4953792 831943 51 4343808 520658 51 2719391 642184 85 3121609 691825 39 7026995 ...
output:
2663416920.97904 1928512891.46544 2270470176.70506 2597243918.16331 1455194752.90886 2183638273.06671 1692789012.78537 2266073869.02243 2496007785.56258 2296006666.68333 1246768433.83332 2503127235.8526 2051884673.88639 1670260383.25294 1329974873.90736 2102267234.92882 2228182778.40602 2065631564.4...
result:
ok 199673 numbers
Test #26:
score: 0
Accepted
time: 337ms
memory: 32136kb
input:
199393 73 8091358 636821 63 3610955 902862 64 5111999 556237 78 6533532 853174 48 686517 962833 17 8744218 893633 70 3721028 529352 98 1162071 874456 32 9296883 502388 30 308699 714994 100 4191990 607788 3 4777744 786151 83 6953281 811671 52 8756665 654068 97 981220 909737 97 6324379 990946 6 730619...
output:
1275130082.97255 1493550552.93089 973568760.578958 1610876608.73415 1917650576.82207 1437555485.98258 745082252.339796 1766089887.56744 1584227879.32143 951064194.587344 2018503334.66066 1219497961.20947 1549263972.68036 930468945.02426 1200936817.50111 2009863971.57807 1971316327.94321 832030635.09...
result:
ok 199393 numbers
Test #27:
score: 0
Accepted
time: 333ms
memory: 33344kb
input:
199875 63 6269819 886681 17 5467813 721870 48 6402860 741591 18 253634 907256 77 2409927 663402 32 762162 815118 11 1743775 756777 7 6657703 601020 44 3859980 976923 47 5417008 792908 74 602223 509641 4 8410806 856919 62 9019038 832694 49 833878 650671 51 9243051 594701 8 9593416 844285 65 9921030 9...
output:
2213856003.1257 1775683281.44448 2166436262.25989 1593306697.44233 1943159460.1901 2266283494.04248 2305962466.387 1714438971.5108 1944956047.58842 1528248633.05341 2319079253.77252 1723020248.55543 1847280158.08893 1659435553.7743 2266943720.69986 1680889406.72102 2380433868.54169 2190616986.85995 ...
result:
ok 199875 numbers
Test #28:
score: 0
Accepted
time: 306ms
memory: 30520kb
input:
199493 80 3646291 6589211 78 3835801 9820358 84 3775894 7887279 69 1403559 7547266 40 2451237 5385669 29 2904241 6950241 65 6125738 7100303 30 3526246 6344762 98 844701 9815023 18 5933784 5196196 40 8335782 9624783 43 5474890 5645503 81 4386861 6220368 39 1603653 7528687 13 6625714 6639631 16 706689...
output:
10214158002.1772 12572146296.1697 12430331164.9296 14939287831.8363 14878605249.4416 11989023568.2113 15721325037.9095 8103362035.45086 17454389308.5589 13196271301.77 15545715392.3254 8679035263.77972 14234787112.3887 17532010551.8647 17037539089.8022 14606370108.1262 8891630212.73566 15975555269.4...
result:
ok 199493 numbers
Test #29:
score: 0
Accepted
time: 323ms
memory: 32108kb
input:
199975 95 9127263 9824246 31 725793 7569723 72 5066755 8332179 9 5123663 8233302 69 4108380 6510726 43 2290963 9771814 6 4148486 9985610 39 3988744 5840025 14 5407800 5718449 27 6075227 5087718 10 9779149 9069107 56 9107953 7713115 56 1419484 6026900 32 6016510 8831954 72 4887544 9655430 27 269667 9...
output:
13937905496.8458 10033778296.3245 15207689460.111 10738075363.2536 11827209682.2949 15492533171.5762 13480084569.6575 14400171178.1764 12982354715.3817 14665395594.5441 12092824838.966 11426666478.288 12620203552.0384 10878713148.3054 14156248631.6328 9771890664.52745 9947544163.72807 11141627833.80...
result:
ok 199975 numbers
Test #30:
score: 0
Accepted
time: 332ms
memory: 32380kb
input:
199075 86 7305724 8126405 81 4918296 6090023 60 1390748 8810642 52 8843766 8148404 10 8463013 7635784 66 4308908 7593387 59 9473744 7133543 48 1820019 5301725 22 9970898 7292121 47 6216669 9208306 84 1222516 8546994 65 405370 9747164 27 8452108 5129623 33 8093724 5839029 26 813730 6967420 39 3538704...
output:
10721879434.659 10797502325.4573 13464577925.9865 16627307131.1128 11616265493.267 12203486352.2815 12909398946.9284 14651536819.8686 13101153739.1432 11291805629.2555 12310694615.6431 15583041967.5044 13108926037.7857 14447914933.6198 13669841962.9984 12037040467.0974 12385880572.0958 16323052278.2...
result:
ok 199075 numbers
Test #31:
score: 0
Accepted
time: 299ms
memory: 19368kb
input:
199199 78151 308067 3510866 94 6357726 1383805 15 2657317 8797531 92 6497312 357768 66 1134727 3432114 28 7985088 8000696 13 147819 1655876 32 4881979 1216259 97 1470964 2232766 25 2929789 5183878 21 4171107 4419118 92 7436038 8910406 32 8680822 8565979 100 5307897 8959910 28 4773869 4268007 57 1347...
output:
335924.968889875 7945776.92377619 3336558.05589574 6583286.32813395 1513151.75933048 12296920.3182004 166073.393624355 5030871.17333364 1820619.97667183 5288502.8097364 4678750.75760769 11701064.2082906 10564865.5150363 11024857.0191818 5717138.80737747 1556387.37836651 6442303.98011936 11739607.820...
result:
ok 199199 numbers
Test #32:
score: 0
Accepted
time: 249ms
memory: 16612kb
input:
199681 594292 5789038 4364536 47 5583361 1412685 3 8981311 1101713 36 217414 8157858 7 5489360 880031 50 7371810 1431418 58 8170568 1612166 41 377610 8562820 5 1000928 2657627 33 8038099 2960000 100 8245697 1329846 4 3766590 9777839 7 5713444 6131898 5 7385110 6125691 82 3035698 5829090 65 4616843 3...
output:
5789045.34409348 5583389.05876741 8981312.85382438 217440.360181527 5489361.48080573 7371812.40861058 8170570.71275063 377624.408438949 1000932.47192121 8038106.81972498 8245699.23769797 3766606.45292045 5713454.31798846 7385125.87967734 3035707.80846116 4616848.23804796 8423434.94322993 5589200.849...
result:
ok 199681 numbers
Test #33:
score: 0
Accepted
time: 254ms
memory: 17324kb
input:
199782 951648 8934366 5026718 9 7440220 1184668 91 272171 3405895 75 6568741 990652 36 2179636 8327948 65 9389755 4862140 7 1160181 6727240 51 840108 5909381 21 597159 8049784 53 8179541 5446522 70 4655931 8305983 17 2366518 645273 81 7779201 3889305 97 6764834 8067280 41 1297528 2614366 76 7885880 ...
output:
8934371.28211902 7440221.24485944 272174.578944105 6568742.04098574 2179644.75108023 9389760.10917902 1160188.06904233 840114.898409916 597167.458783079 8179546.72325272 4655942.07275379 2366518.67805848 7779206.97650707 6764842.47716803 1297530.74719854 7885881.62523538 6005127.56544647 3672394.944...
result:
ok 199782 numbers
Test #34:
score: 0
Accepted
time: 334ms
memory: 31804kb
input:
199013 2 5648444 6390891 30 4583777 4765203 91 6002297 9967339 67 2920106 5046393 16 1078536 9551957 15 4208514 8778670 95 6524454 7530040 44 5903729 8501282 33 3694577 8408932 62 771162 6157066 4 9717159 3022531 97 8386385 467293 82 5854615 1902200 68 1266157 8997519 45 2513227 4669366 78 8418928 5...
output:
422330846578.997 217302476200.056 388908111736.452 447421455718.804 473670311290.8 321064635269.453 403413314451.734 435703578221.707 378175228790.52 488886966001.814 140471687707.959 28129828435.5603 127607157606.547 417283372283.303 240842409817.681 404355678120.142 488956614237.8 321584033228.498...
result:
ok 199013 numbers
Test #35:
score: 0
Accepted
time: 340ms
memory: 33112kb
input:
199114 46 6162548 7053073 83 6440636 9761378 79 7293157 2271521 6 4304566 2846483 49 2735679 1967170 41 6226459 2209392 48 1849712 7677818 53 6366227 815139 41 593319 8833793 82 912605 3676292 74 6127392 4965964 98 4716936 6302023 45 2887238 4626902 61 5679015 5971812 3 8439414 6230450 94 6654831 42...
output:
13270785737.0927 15888659942.5135 19830440328.5434 10219121022.5935 8794729532.68058 8508652523.29725 16746925846.2831 4058690357.13369 15023451061.3322 9036976049.47022 9193518426.71134 16576759694.159 12350448518.2113 21371543825.4221 11263961776.6547 8266223188.26687 14407020264.6972 13644038520....
result:
ok 199114 numbers
Test #36:
score: 0
Accepted
time: 322ms
memory: 32544kb
input:
199596 87 9307876 2682550 45 5666271 9533362 67 3617151 4575704 58 8024669 5679277 86 7090312 4447791 60 5613182 5640114 89 4839326 2601404 63 4197502 3128996 49 123283 4291358 90 8718404 6419710 49 5235115 1942100 11 3316864 2136753 20 9919861 7417013 58 5058738 3137593 50 6701243 2758829 1 9923868...
output:
5524614624.60397 8842445165.14314 6717217887.1529 5954728955.37284 6451381042.31311 5777733893.78579 4118838152.13812 5808315903.4871 4612176056.1528 8610704084.93587 9364167101.82695 7944757485.17094 8539108645.90896 5735633416.11041 11378771214.3162 4837540165.37323 953633964.009088 10565691238.45...
result:
ok 199596 numbers
Test #37:
score: 0
Accepted
time: 326ms
memory: 31652kb
input:
199697 39 4788847 3344732 94 2556263 4529537 55 4908011 1912590 98 6711639 8446664 20 3780588 1895708 82 2597993 9070836 41 7828941 7781885 80 4660000 475557 70 4686381 4907707 15 8859846 8906232 19 6678482 3885532 19 4614282 7971483 95 6952484 9950228 58 7135952 303374 4 4963073 4576809 17 495414 1...
output:
8080516207.39613 15379520637.7416 4704955625.28516 23724826976.6238 5498253763.45826 21858676687.8759 16920641339.3985 1714686622.73966 23125936060.8547 23927692271.5764 21539830987.9691 15560365236.1174 20731573992.0944 14592285657.3323 22555069203.1186 15571096717.9028 10020709746.9224 19126872336...
result:
ok 199697 numbers
Test #38:
score: 0
Accepted
time: 343ms
memory: 33468kb
input:
199798 83 2967307 8974210 56 9446256 4301520 43 6198872 9184068 37 431742 1022562 61 8135221 4567817 97 1984715 7468854 82 5851688 2896959 89 155631 2789414 78 4216345 365272 23 3968155 6425459 94 3088715 861669 20 8247345 4063108 70 9018241 2740338 47 1548808 7277667 63 889259 6137892 24 8731318 36...
output:
9585283617.95985 8084038822.53111 10472903001.0848 1903914662.78517 4825951818.89849 7687860874.44797 3528421731.61974 3801412971.62176 1828843662.40486 6405828305.00643 4479058921.66928 5688131849.58805 5708000433.46289 8615588401.13124 10519349299.7114 61411050.133919 686981446.40368 926382024.662...
result:
ok 199798 numbers
Test #39:
score: 0
Accepted
time: 2ms
memory: 6100kb
input:
1360 49 9871429 9779574 40 9989546 534733 28 3556340 8555939 45 2305081 5937120 29 5096830 6921998 49 7191025 9278305 8 1298498 9627142 14 671882 3049863 76 7402068 6967792 30 4959332 8268659 69 4691507 7797825 22 2723063 1478222 99 2602570 2927804 66 9779683 6186660 50 706855 189678 58 8926331 5264...
output:
123331351.30786 34603328.3370537 117294057.853424 118724756.222695 109278783.858189 137076595.222914 134482946.239141 34527002.9992889 122234510.150622 103418304.970579 128510981.489846 17110978.0926793 51474075.0451887 106097823.69213 1057524.68944885 73357616.3125882 135935222.171997 68134928.9148...
result:
ok 1360 numbers
Test #40:
score: 0
Accepted
time: 6ms
memory: 5988kb
input:
1842 93 5352399 376348 90 6879538 306716 20 9880335 860121 93 6025185 3737210 70 9451463 9594107 79 9208970 7676323 49 9321246 9774920 23 6167514 5363720 84 1965166 2616845 42 67641 5979374 47 6134874 4773961 31 9053615 7312952 74 9635193 5717915 63 1856896 8128249 5 8968685 1750762 73 2129100 39552...
output:
7987080.24697098 20278894.5875759 18320294.061011 47350535.1992692 73982532.3305225 79242940.079601 91559848.2606005 53356053.0901793 45696221.8319254 61057205.3520112 78364243.7116484 68764097.5244881 66605259.4351264 97835462.2094778 29811318.4123715 51047928.0782184 45401515.195059 84861071.09094...
result:
ok 1842 numbers
Test #41:
score: 0
Accepted
time: 2ms
memory: 6024kb
input:
1562 34 8497727 1038529 44 8736396 5111403 4 1171194 3164303 36 9745289 6570004 3 6141739 7042024 94 3562558 1107045 97 4646504 4698505 36 8965656 7934473 92 1495130 3041706 58 5175950 3498600 17 209463 6717394 43 7653543 3147682 53 1700949 3475322 59 1236619 326734 63 4894871 3311845 81 5398137 238...
output:
56900292.5008926 223642699.080262 139709814.644438 225822068.409826 132960879.399121 25062361.1712136 172965317.483263 146396021.551932 94295992.1866997 193221471.417159 177992215.180595 114510915.233796 104870587.917751 4380449.19804167 83564411.8015284 183113596.499792 30909569.1224898 197264086.3...
result:
ok 1562 numbers
Test #42:
score: 0
Accepted
time: 2ms
memory: 6048kb
input:
1043 86 1709320 1892199 5 2995165 5074875 96 2462055 5468486 76 6096614 4370095 41 496371 4489941 16 613636 9505064 42 7636118 4846283 46 4461287 248330 13 6058228 3466567 75 5317392 6050530 96 1652830 8660826 52 8950961 4015116 24 8733572 1041240 56 3313833 7492515 10 3156701 9905633 96 8667174 107...
output:
55728508.1056343 24155440.3416811 30021799.4647321 43517016.2623287 53263756.3154177 51213710.9157231 43989691.5870277 12049581.5876006 26940157.579823 32066791.2778446 48039943.1704896 50652583.1258813 18099262.9891914 58206179.4820194 40418449.7456188 15434825.0330264 25997939.8960351 10580800.007...
result:
ok 1043 numbers
Test #43:
score: 0
Accepted
time: 5ms
memory: 6072kb
input:
1525 30 7190292 2554381 59 9885158 4846858 84 8786049 7772668 16 9816718 2170185 74 7186648 1937858 39 7664716 7968490 83 5658866 4994061 55 4923786 2562187 21 621325 4148323 87 5458834 8793948 66 3096197 604258 57 2584023 9849845 91 733061 8798647 57 7726690 9434104 64 1418530 6690908 4 1869943 473...
output:
99509524.6594757 124746768.263116 238953615.193232 75827976.7067994 110266382.422736 167850000.898466 161967658.505839 184761418.152152 87603266.8933285 190877016.800509 24126960.8829436 174123039.560946 196206527.541234 197568772.609293 252320975.472601 180161316.747451 52195835.5711151 239545577.1...
result:
ok 1525 numbers
Test #44:
score: 0
Accepted
time: 3ms
memory: 5868kb
input:
316 59 9188975 3868239 10 1555155 115859 26 5453579 247042 72 2822282 4185205 49 82066 6588164 75 5670503 7171636 83 9577189 1881903 17 7935150 4796220 33 4738599 2350579 56 417510 597470 97 647601 4861443 40 5843081 6719640 5 1819841 6829760 9 2504145 9651623 92 1334814 7014371 46 2616434 1788240 7...
output:
25295770.4864112 1657034.38034437 5846332.30328343 14063725.1949886 1173590.54365461 18383473.7289528 21350187.7635467 22220128.5042495 11031724.84269 502932.661607208 5221978.62580424 26841423.8436709 26317074.2741672 15961440.5160445 16912327.1804459 4295986.51730828 24097114.8499029 26034526.0215...
result:
ok 316 numbers
Test #45:
score: 0
Accepted
time: 0ms
memory: 5776kb
input:
139 8 9703080 4465013 64 3412014 9887842 14 6744440 2551224 12 9173609 1985295 87 4436699 4036081 94 24091 5569654 27 4902447 6805489 30 733291 2142781 49 9301697 7999632 69 558952 3340888 72 4722191 6613388 45 4443010 2554370 75 3885598 4587166 14 6917003 6817404 50 9596645 3608158 61 5885471 52546...
output:
49808572.7821732 83536742.1910106 71141235.2526023 26003670.6994446 32580177.9785774 64511504.304906 71851346.0028444 18137195.0125862 61360909.2880492 18439854.1815792 64805623.2968818 27308308.83058 76425232.5823343 64079292.0164071 45590861.5917502 67390688.7878576 72238289.4785247 63700134.79301...
result:
ok 139 numbers
Test #46:
score: 0
Accepted
time: 0ms
memory: 5880kb
input:
363 48 2848407 94490 13 2637649 9916722 2 732789 4855406 51 2893711 4561193 20 1126975 6708190 16 7075171 9191864 76 7892061 1920562 39 6228923 4456638 61 3864794 8424493 85 5667261 860114 46 6165558 8556820 54 773561 8389099 50 918220 7120381 3 6296726 9015889 5 5522831 5169242 69 4121374 8912580 9...
output:
3564198.07924044 38384664.5426366 12056978.27604 33035516.6754693 35505049.3132508 29686269.6114427 20274188.2195297 23331133.1863118 25006369.1451058 9896480.71162077 31484838.9086642 26966227.7546105 38143885.8151538 37952386.1987948 22945751.3529248 24037696.977008 37021964.765407 13730187.122482...
result:
ok 363 numbers
Test #47:
score: 0
Accepted
time: 2ms
memory: 5836kb
input:
186 92 8329378 5980864 75 4494508 4656001 90 7056784 7159588 95 6613815 2361283 57 448474 4156107 31 1428759 2622586 21 881675 2068340 48 1724555 6770495 69 3394759 8849354 1 5808704 3346636 17 7608925 5532956 67 7037846 4480725 29 582066 9910492 4 8373940 957478 59 3784660 6730326 80 2357277 760319...
output:
8451520.45024607 4748304.77300951 7286051.44929486 6806855.29868059 562187.728819996 2067663.75227121 1089997.16000378 2362423.38504563 7695970.20881089 6515934.52319605 7688659.88155034 7434423.29541243 3670385.39828084 8409160.32105186 3858730.1638587 3163201.49027392 7938737.23447498 1395873.5176...
result:
ok 186 numbers
Test #48:
score: 0
Accepted
time: 1ms
memory: 5844kb
input:
156 37 1474705 1610342 28 1384500 9460688 78 8347644 9463771 35 5300785 161374 90 7138751 6636728 57 8479838 6053308 62 8904423 2216118 58 2187053 4117056 86 7957857 4498407 18 917012 6090054 95 6716648 2443685 79 5704041 5282751 100 2647822 2443706 1 7753663 8123259 18 2046490 3515601 92 5626314 12...
output:
2957012.99677394 6972018.88717373 19389936.7894575 5447846.48853603 16878683.4602865 16710975.8636937 13198424.8285543 4556052.54401116 19208531.8160557 1680056.50346844 9897221.71725829 11204977.0716202 21648556.0338804 20124373.985126 3676386.99863712 11331614.8242576 7229221.21641004 16452677.233...
result:
ok 156 numbers