Submission #443745

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
443745	2021-07-12T01:50:21 Z	YimingHuang47	Balloons (CEOI11_bal)	C++14	100 / 100	326 ms	10460 KB

//problem: https://oj.uz/problem/view/CEOI11_bal
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <stack>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vll = vector<vl>;
using vii = vector<vector<int>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
#define pb push_back
#define f first
#define s second
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define lb lower_bound
#define ub upper_bound 
const int MOD = 1e9+7;
const ll INF = 1e18;
template<class T> bool ckmin(T& a, const T& b){return b < a ? a = b, 1 : 0;}
template<class T> bool ckmax(T& a, const T& b){return a < b ? a = b, 1 : 0;}
void setIO(string name=""){
  freopen((name+".in").c_str(),"r",stdin);
  freopen((name+".out").c_str(),"w",stdout);
}


int N;
const int maxn = 200005;
int P[maxn], R[maxn];
long double fR[maxn];
long double compute(int a, int b){
  return (long double)(P[b]-P[a])*(P[b]-P[a])/(4*fR[a]);
}
int main() {
  //freopen("input.txt","r",stdin);
  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> P[i] >> R[i];
  }
  stack<int> s;
  for(int b = 0; b < N; b++){
    fR[b] = R[b];
    while(s.size()){
      int a = s.top();
      long double rB = compute(a,b);
      ckmin(fR[b],rB);
      if(fR[b] > fR[a]){
        s.pop();
      }
      else{
        break;
      }
    }
    s.push(b);
  }
  for(int i = 0; i < N; i++){
    printf("%.3Lf\n",fR[i]);
  }
}

Compilation message

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

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	10 numbers

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	2 numbers

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	304 KB	505 numbers

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	332 KB	2000 numbers

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	1100 KB	20000 numbers

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	2536 KB	50000 numbers
2	Correct	62 ms	2828 KB	49912 numbers

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	133 ms	4932 KB	100000 numbers

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	146 ms	5724 KB	115362 numbers
2	Correct	149 ms	6340 KB	119971 numbers

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	193 ms	7464 KB	154271 numbers
2	Correct	326 ms	10440 KB	200000 numbers

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	241 ms	9260 KB	200000 numbers
2	Correct	275 ms	10460 KB	199945 numbers