oj.uz

Submission #485611

# Submission time Handle Problem Language Result Execution time Memory
485611 2021-11-08T14:48:16 Z AkiYuu Balloons (CEOI11_bal) C++17
100 / 100
 209 ms 11312 KB 
#include <bits/stdc++.h>
#define task "GROUP"
#define ll long long
#define ld long double
#define pb(u) emplace_back(u)
#define ffw(i,a,b) for (ll i = a; i <= b; i++)
#define fbw(i,b,a) for (ll i = b; i >= a; i--)
#define adj(v,adj,u) for (auto v : adj[u])
#define rep(i,a) for (auto i : a)
#define reset(a) memset(a, 0, sizeof(a))
#define sz(a) a.size()
#define all(a) a.begin(),a.end()

using namespace std;

inline namespace FastIO {
	const int BSZ = 1<<15;
	char ibuf[BSZ]; int ipos, ilen;
	char nc() { //
		if (ipos == ilen) {
			ipos = 0; ilen = fread(ibuf,1,BSZ,stdin);
			if (!ilen) return EOF;
		}
		return ibuf[ipos++];
	}
	void readstr(string& x) {
		char ch; while (isspace(ch = nc()));
		do { x += ch; } while (!isspace(ch = nc()) && ch != EOF);
	}

	template<class T> void readnum(T& x){
		char ch; int sgn = 1;
		while (!isdigit(ch = nc())) if (ch == '-') sgn *= -1;
		x = ch-'0'; while (isdigit(ch = nc())) x = x*10+(ch-'0');
		x *= sgn;
	}
}

const int mxn = 1e6 + 5;
typedef pair<ld, ld> ii;

void fastio(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
//	freopen(task".inp", "r", stdin);
//	freopen(task".out", "w", stdout);
}


//                       _oo0oo_
//                      o8888888o
//                      88" . "88
//                      (| -_- |)
//                      0\  =  /0
//                    ___/`---'\___
//                  .' \|     |// '.
//                 / \|||  :  |||// \
//                / _||||| -:- |||||- \
//               |   | \\  -  /// |   |
//               | \_|  ''\---/''  |_/ |
//               \  .-\__  '-'  ___/-. /
//             ___'. .'  /--.--\  `. .'___
//          ."" '<  `.___\_<|>_/___.' >' "".
//         | | :  `- \`.;`\ _ /`;.`/ - ` : | |
//         \  \ `_.   \_ __\ /__ _/   .-` /  /
//     =====`-.____`.___ \_____/___.-`___.-'=====
//

ld pos[mxn], r[mxn];
stack < ii > st;
ll n;

ld sqr(ld x){
    return x*x;
}
void solve(){
    cin >> n;
    ffw(i,1,n) cin >> pos[i] >> r[i];
    cout << setprecision(3) << fixed <<  r[1] << '\n';
    st.push(ii(pos[1], r[1]));
    ffw(i,2,n){
        while (sz(st)){
            auto [POS,R] = st.top();
            r[i] = min(r[i], sqr(POS - pos[i])/(4*R) );
            if (r[i] > R) st.pop();
            else break;
        }
        st.push(ii(pos[i], r[i]));
        cout << setprecision(3) << fixed <<  r[i] << '\n';
    }
}

int main(){
	fastio();
	solve();
}

Compilation message

bal.cpp:57:1: warning: multi-line comment [-Wcomment]
   57 | //                 / \|||  :  |||// \
      | ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 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 21 ms 1048 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 2628 KB 50000 numbers
2 Correct 62 ms 3028 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 4548 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 5236 KB 115362 numbers
2 Correct 128 ms 6752 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 6772 KB 154271 numbers
2 Correct 204 ms 11052 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 8176 KB 200000 numbers
2 Correct 204 ms 11312 KB 199945 numbers