Submission #546952

#	Time	Username	Problem	Language	Result	Execution time	Memory
546952		mgl_diamond	Balloons (CEOI11_bal)	C++17	30 / 100	2082 ms	3352 KiB

bal

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<double, double>;

#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << "\n"
#define all(x) x.begin(), x.end()

template<class T> bool umax(T &a, T b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool umin(T &a, T b) { if (a>b) { a=b; return 1; } return 0; }

void setIO(string name="") {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (name.size()) freopen((name+".inp").c_str(),"r",stdin);
	if (name.size()) freopen((name+".out").c_str(),"w",stdout);
}

double dis(ii a, ii b) {
	double x=a.fi-b.fi, y=a.se-b.se;
	return x*x+y*y;
}

const int mxN=200000;
int n;
double x[mxN], r[mxN];

bool f(int mx, double dia) {
	for(int i=0; i<mx; ++i) {
		//debug(dis({x[i], r[i]}, {x[mx], dia}));
		//debug(r[i]+dia);
		double val=dis({x[i], r[i]}, {x[mx], dia});
		double tmp=r[i]+dia;

		//cout << sqrt(val) << " " << tmp << "\n";
		if (val<tmp*tmp) return 0;
	}
	return 1;
}

int main() {
	//setIO("input");
	cin >> n;
	for(int i=0; i<n; ++i)
		cin >> x[i] >> r[i];

	for(int i=1; i<n; ++i) {
		double lb=0, rb=r[i], mb;
		while (rb-lb>0.00001) {
			mb=(lb+rb)/2;
			if (f(i, mb)) lb=mb, r[i]=mb;
			else rb=mb;
		}
	}

	for(int i=0; i<n; ++i)
		cout << r[i] << " ";
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10