oj.uz

답안 #1109345

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109345 2024-11-06T13:25:34 Z Plot_Twist Balloons (CEOI11_bal) C++17
10 / 100
 115 ms 8264 KB 
#include<bits/stdc++.h>
#include<chrono>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

using namespace std;
using namespace chrono;
#define ll long long
#define vl vector<long long>
#define endl '\n'
const int MOD = 1e9 + 7;
void inputv(vl &v) {for(int i = 0; i < (ll)v.size(); i++) cin>>v[i];}
void printv(vl v) {for(auto i : v) cout<<i<<" ";cout<<endl;}

#define ONLINE_JUDGE

#ifndef ONLINE_JUDGE
#include "template.cpp"
#else
#define debug(...)
#define debugArr(...)
#endif

#define int long long

#define ld long double

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;

int n;
vector<int>arr;
vector<int>maxRad;
vector<ld>ans;

int check(int x1, int x2, ld rad1, ld rad2) {
    ld temp = rad1/rad2;
    int high = 1e16;
    int ans = -1;
    int low = x2+1;
    while(low>high) {
        int mid = (low+high)/2;
        ld t = (1 + (((ld)x2 - x1)/((ld)mid - x2)));
        t *= t;
        if(t>=temp) {
            ans = mid;
            low = mid+1;
        }
        else high = mid-1;
    }
    return ans;
}

signed main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        freopen("error.txt","w",stderr);
    #endif
    ios::sync_with_stdio(false); cin.tie(NULL);
    int ts = 1;

    #ifndef ONLINE_JUDGE
    auto start = duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();
    #endif
    while(ts--) {
        cin>>n;
        arr = maxRad = vector<int>(n);
        for(int i = 0; i < n; i++) cin>>arr[i]>>maxRad[i];
        stack<pair<int,int>>st;
        ans = vector<ld>(n);
        ans[0] = maxRad[0];
        st.push({0,-1});
        for(int i = 1; i < n; i++) {
            while(st.top().second != -1 && st.top().second < arr[i]) st.pop();
            int prev = st.top().first;
            ld rad = min((ld)maxRad[i], ((ld)arr[i]-(ld)arr[prev])*((ld)arr[i]-(ld)arr[prev])/((ld)4.0*ans[prev]));
            ans[i] = rad;
            while(!st.empty() && ans[st.top().first] <= rad) st.pop();
            if(!st.empty()) {
                prev= st.top().first;
                int temp = check(arr[prev], arr[i], ans[prev], ans[i]);
                if(temp!=-1) st.push({i,temp});
            }
            else {
                st.push({i, -1});
            }
        }
        cout<<fixed<<setprecision(3);
        for(int i = 0; i < n; i++) cout<<ans[i]<<endl;

    }
    #ifndef ONLINE_JUDGE
    auto stop = duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();
    cerr << "Took " << stop - start << "ms" << endl;
    #endif
    
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 336 KB 7th numbers differ - expected: '11.4400000000', found: '81.0000000000', error = '69.5600000000'
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 336 KB 13th numbers differ - expected: '2.3960000000', found: '6.2550000000', error = '3.8590000000'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 336 KB 3rd numbers differ - expected: '121.0000000000', found: '123.0000000000', error = '2.0000000000'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 1104 KB 3rd numbers differ - expected: '211.0000000000', found: '213.0000000000', error = '2.0000000000'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 2268 KB 5th numbers differ - expected: '15395.0000000000', found: '15396.0000000000', error = '1.0000000000'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 59 ms 4472 KB 3rd numbers differ - expected: '7936.0000000000', found: '10352.0000000000', error = '2416.0000000000'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 58 ms 4936 KB 5th numbers differ - expected: '5054.0000000000', found: '5055.0000000000', error = '1.0000000000'
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 90 ms 6580 KB 3rd numbers differ - expected: '1872.0000000000', found: '1874.0000000000', error = '2.0000000000'
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 115 ms 8264 KB 3rd numbers differ - expected: '2960.0000000000', found: '2962.0000000000', error = '2.0000000000'
2 Halted 0 ms 0 KB -