oj.uz

답안 #1115938

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1115938 2024-11-21T05:36:05 Z JeffLegendPower Balloons (CEOI11_bal) C++17
10 / 100
 442 ms 9288 KB 
// https://oj.uz/problem/view/CEOI11_bal

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define plli pair<ll, int>
#define pll pair<ll, ll>
#define pii pair<int, int>
// Usage: FOR(i, 0, N) {...}
#define FOR(i, start, end) for(int i = start; i < end; i++)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

struct comp {
    bool operator() (const plli& a, const plli& b) const {
        return a < b;
    }
};

typedef tree<plli, null_type, comp, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;


// Segtree start
const int Nmax = 1e5;  // limit for array size
int N;  // array size
int t[2 * Nmax];

int oper(int a, int b) {
    return a + b;
}

void build() {  // build the tree
  for (int i = N - 1; i > 0; --i) t[i] = oper(t[i<<1], t[i<<1|1]);
}

void modify(int p, int value) {  // set value at position p
  for (t[p += N] = value; p > 1; p >>= 1) t[p>>1] = oper(t[p], t[p^1]);
}

int query(int l, int r) {  // on interval [l, r)
  int res = 0;
  for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
    if (l&1) res = oper(res, t[l++]);
    if (r&1) res = oper(res, t[--r]);
  }
  return res;
}
// Segtree end

#define pdd pair<double, double>

int main() {
    // Comment out for interactive problems
    ios::sync_with_stdio(false);
	cin.tie(nullptr);

    // let x be the radius of current balloon
    // let y be the radius of some previous balloon
    // let d be the distance between current balloon and some previous balloon

    // looking at just the current balloon with radius x and a previous balloon with radius y and the balloons are a distance d apart
    // we can create a triangle that relates x, y, and d assuming the 2 balloons touch
    // and get that (y-x)^2 + d^2 = (y+x)^2
    // y^2 - 2xy + x^2 + d^2 = y^2 + 2xy + x^2
    // d^2 = 4xy
    // x = d^2/4y
    // so now x is equal to the min of the max radius of the balloon and the min across all x = d^2/4y for all balloons before the current one
    
    // this takes O(n^2) time, but we can optimize it to O(n)
    // lets ignore the maximum radius bound for now
    // first notice that lets say for balloon i, the bounding balloon is j
    // say that bound(a) = bound caused by balloon a on balloon i
    // we know that for any balloon k < j, bound(k) >= bound(j)
    // now lets say our distance increases by m. we can show that all k < j will never be a bounding balloon ever again because
    // for all k < j, d[k to i] > d[j to i], and since we are calculating d^2, we see that because d[k to i] > d[j to i],
    // (d[k to i] + m)^2 > (d[j to i] + m)^2 while the denominator stays constant, which means that bound(k) will increase more than bound(j)
    // this means that once j is a bounding balloon, we never have to look before j again
    // UPDATE turns out that this is not needed to solve this problem :skull:

    // observation: if radius(j) > radius(k<j) then balloon j will be a better bounding balloon than balloon k
    // and lets say for current balloon i, radius(j<i) > radius(i)

    int N; cin >> N;

    pdd b[N];
    for (int i = 0; i < N; i++) cin >> b[i].first >> b[i].second;

    cout << fixed << setprecision(3);

    double r[N];

    stack<int> s;
    for (int i = 0; i < N; i++) {
        r[i] = b[i].second;
        while (!s.empty() && r[s.top()] <= r[i]) {
            int j = s.top();
            r[i] = min(r[i], (b[i].first - b[j].first) * (b[i].first - b[j].first) / (4*r[j]));
            s.pop();
        }

        if (!s.empty()) {
            int j = s.top();
            r[i] = min(r[i], (b[i].first - b[j].first) * (b[i].first - b[j].first) / (4*r[j]));
        }

        s.push(i);

        // for (int j = i - 1; j >= 0; j--) r[i] = min(r[i], (b[i].first - b[j].first) * (b[i].first - b[j].first) / (4*r[j]));
        cout << r[i] << endl;
    }
}

Compilation message

bal.cpp: In function 'void setIO(std::string)':
bal.cpp:22:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bal.cpp:23:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 336 KB 5th numbers differ - expected: '17.1630000000', found: '99.0000000000', error = '81.8370000000'
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 336 KB 30th numbers differ - expected: '5.5990000000', found: '14.9870000000', error = '9.3880000000'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 488 KB 148th numbers differ - expected: '8.2380000000', found: '26.0000000000', error = '17.7620000000'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 1104 KB 196th numbers differ - expected: '100.7250000000', found: '111.0000000000', error = '10.2750000000'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 116 ms 2632 KB 14197th numbers differ - expected: '2.2500000000', found: '2.3440000000', error = '0.0940000000'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 239 ms 4936 KB 7456th numbers differ - expected: '0.7080000000', found: '1.4120000000', error = '0.7040000000'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 271 ms 5712 KB 4775th numbers differ - expected: '0.0420000000', found: '3342.7530000000', error = '3342.7110000000'
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 354 ms 7612 KB 1730th numbers differ - expected: '5.6890000000', found: '6.8060000000', error = '1.1170000000'
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 442 ms 9288 KB 2716th numbers differ - expected: '22.1690000000', found: '43.0000000000', error = '20.8310000000'
2 Halted 0 ms 0 KB -