| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1015885 |
2024-07-07T02:14:43 Z |
Keshav211 |
Balloons (CEOI11_bal) |
C++14 |
|
170 ms |
41860 KB |
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <chrono>
#include <string>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <climits>
#include <bitset>
#define all(x) (x).begin(), (x).end()
#define vec(n) vll arr(n);
#define printarr(arr) for(auto i:arr){cout<<i<<" ";}cout<<endl;
#define printdict(dict) for(auto i:dict)cout<<i.first<<": "<<i.second<<endl;
#define printadj(adj) for(ll i=0;i<n;i++){if(!adj[i].empty()){cout<<i<<": ";printarr(adj[i])}}
#define read(arr); for(ll i=0;i<arr.size();i++) cin>>arr[i];
#define readundirected(m) for(ll i=0;i<m;i++){ll a,b; cin>>a>>b; a--;b--; adj[a].pb(b);adj[b].pb(a);}
#define readdirected(m) for(ll i=0;i<m;i++){ll a,b; cin>>a>>b; a--;b--; adj[a].pb(b);}
#define readundirectedweighted(m) for(ll i=0;i<m;i++){ll a,b,w; cin>>a>>b>>w; a--;b--; adj1[a].pb({b,w});adj1[b].pb({a,w});}
#define readdirectedweighted(m) for(ll i=0;i<m;i++){ll a,b,w; cin>>a>>b>>w; a--;b--; adj1[a].pb({b,w});}
#define readfunc(n) for(ll i=0;i<n;i++){ll a;cin>>a;a--;func_adj[i]=a;}
#define grid(n,m) for (ll i=1;i<=n;i++){for (ll j=1;j<=m;j++) cin>>graph[i][j];}
#define vll vector<ll>
#define sll set<ll>
#define msll multiset<ll>
#define qll queue<ll>
#define pll pair<ll,ll>
#define str string
#define pb push_back
#define ll long long
#define ld long double
using namespace std;
const str alph="abcdefghijklmnopqrstuvwxyz";
const str capalph="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ll inf=5e5+1;
const ll graph_size=1e3+2;
const ll mod=1e9+7;
const ld pi=3.141592653589793238462643383279502884197;
const ll large=1e18;
const ll small=-1e18;
vll adj[inf];
vector<pll> adj1[inf];
bool visited[inf];
ll parent[inf];
ll distance[graph_size][graph_size];
char graph[graph_size][graph_size];
vector<pll> directions={{0,-1},{-1,0},{1,0},{0,1}};
bool floodfill_visited[graph_size][graph_size];
ll floodfill_level[graph_size][graph_size];
pll floodfill_parent[graph_size][graph_size];
// Fast Input/Output
void fastio(){
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
}
// File Input/Output
str fileio(const string&filePath=__FILE__){
size_t lastSlash=filePath.find_last_of('/');
size_t lastDot=filePath.rfind('.');
return filePath.substr(lastSlash+1,lastDot-lastSlash-1);
}
// For Yes Or No Problems
str yes_or_no(bool test){
if (test){
return "YES";
}
return "NO";
}
ll n,m,q;
ld radius(pair<ld,ld> coord1,ld x2){
ld x1=coord1.first;
ld r1=coord1.second;
return (((x2-x1)*(x2-x1)/(ld)(4))/r1);
}
int main(){
// auto start_time=chrono::steady_clock::now();
fastio();
// str filename=fileio();
// ifstream cin(filename+".in");
// ofstream cout(filename+".out");
ll t=1;
// cin>>t;
while (t--){
cin>>n;
vector<pair<ld,ld>> arr(n);
for (ll i=0;i<n;i++){
cin>>arr[i].first>>arr[i].second;
}
stack<pair<ld,ld>> balloons;
vector<ld> ans(n);
for (ll i=0;i<n;i++){
ld curr=arr[i].second;
while (!balloons.empty()){
pair<ld,ld> balloon=balloons.top();
ld curr_r=radius(balloon,arr[i].first);
curr=min(curr,curr_r);
if (curr>=balloon.second){
balloons.pop();
continue;
}
break;
}
balloons.push({arr[i].first,curr});
ans[i]=curr;
}
for (auto i:ans){
cout<<setprecision(20)<<i<<" ";
}
}
// auto end_time=chrono::steady_clock::now();
// auto elapsed_time=chrono::duration_cast<chrono::milliseconds>(end_time-start_time);
// cout<<"Elapsed time: "<<elapsed_time.count()<<" milliseconds\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
23896 KB |
10 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
23900 KB |
2 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
23896 KB |
505 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23900 KB |
2000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
25424 KB |
20000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
28212 KB |
50000 numbers |
| 2 |
Correct |
48 ms |
28240 KB |
49912 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
32084 KB |
100000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
33452 KB |
115362 numbers |
| 2 |
Correct |
101 ms |
34752 KB |
119971 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
132 ms |
36688 KB |
154271 numbers |
| 2 |
Correct |
160 ms |
41776 KB |
200000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
170 ms |
39808 KB |
200000 numbers |
| 2 |
Correct |
150 ms |
41860 KB |
199945 numbers |
