# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
489645 | Yuisuyuno | Balloons (CEOI11_bal) | C++14 | 3 ms | 460 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Nguyen Huu Hoang Minh
#include <bits/stdc++.h>
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define reset(x) memset(x, 0,sizeof(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define N 2005
#define remain(x) if (x > MOD) x -= MOD
#define ii pair<int, int>
#define iiii pair< ii , ii >
#define viiii vector< iiii >
#define vi vector<int>
#define vii vector< ii >
#define bit(x, i) (((x) >> (i)) & 1)
#define Task "test"
#define int long long
using namespace std;
typedef long double ld;
const int inf = 1e10;
const int minf = -1e10;
int n;
double x[N], r[N];
double R[N];
void readfile()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
if (fopen(Task".inp","r"))
{
freopen(Task".inp","r",stdin);
//freopen(Task".out","w",stdout);
}
cin >> n;
for(int i=1; i<=n; i++){
cin >> x[i] >> r[i];
}
}
double check(int pos, int pre){
//(x[pre],R[pre])
//(x[pos],R[pos])
//dis*dis = (xpre-xpos)*(xpre-xpos) + (Rpre-R)*(Rpre-R) = Rpre^2 + 2*Rpre*R + R^2
//(xpre-xpos)*(xpre-xpos) = 4*Rpre*R
double R_cur = (x[pre]-x[pos])*(x[pre]-x[pos])/4/R[pre];
return R_cur;
}
void proc()
{
R[1] = r[1];
stack<int> st;
st.push(1);
for(int i=2; i<=n; i++){
double RR;
while (st.size()){
int id = st.top();
double xi = x[id];
double ri = R[id];
RR = min(r[i],(xi-x[i])*(xi-x[i])/4/ri);
if (RR > ri+1e-9) st.pop();
else break;
}
st.push(i);
R[i] = RR;
}
cout << setprecision(3) << fixed;
for(int i=1; i<=n; i++) cout<<R[i]<<'\n';
}
signed main()
{
readfile();
proc();
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |