oj.uz

답안 #489647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
489647 2021-11-23T13:53:41 Z Yuisuyuno Balloons (CEOI11_bal) C++14
100 / 100
 213 ms 10200 KB 
//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 200005
#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()
{
    stack<pair<double,double>> st;
    st.push(make_pair(x[1],r[1]));
    for(int i=2; i<=n; i++){
        while (st.size()){
            double x1 = st.top().fi;
            double r1 = st.top().se;
            r[i] = min(r[i],0.25*(x1-x[i])*(x1-x[i])/r1);
            if (r[i]>r1) st.pop();
            else break;
        }
        st.push(make_pair(x[i],r[i]));
    }
    cout << setprecision(3) << fixed;
    for(int i=1; i<=n; i++) cout<<r[i]<<'\n';
}

signed main()
{
    readfile();
    proc();
    return 0;
}

Compilation message

bal.cpp: In function 'void readfile()':
bal.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(Task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB 10 numbers

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB 2 numbers

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB 505 numbers

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 372 KB 2000 numbers

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 872 KB 20000 numbers

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 2312 KB 50000 numbers
2 Correct 60 ms 2772 KB 49912 numbers

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 4164 KB 100000 numbers

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 4892 KB 115362 numbers
2 Correct 110 ms 6256 KB 119971 numbers

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 193 ms 6272 KB 154271 numbers
2 Correct 174 ms 10200 KB 200000 numbers

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 7580 KB 200000 numbers
2 Correct 176 ms 10084 KB 199945 numbers