Submission #593806

#	Time	Username	Problem	Language	Result	Execution time	Memory
593806		Gaurav__Arora	Balloons (CEOI11_bal)	C++14	100 / 100	165 ms	10224 KiB

bal

/* Gaurav Arora */
//******************************************************TEMPLATE START******************************************************************
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template <typename num_t>
// using ordered_set = tree<num_t, null_type, less_equal<num_t>, rb_tree_tag, tree_order_statistics_node_update>;
using namespace chrono;
#define gc getchar_unlocked
#define inf INT_MAX
#define minf INT_MIN
#define ff first
#define ss second
#define mp make_pair
#define nline "\n"
#define pb push_back
#define sz(x) ((int)(x).size())
#define len(x) ((int)(x).length())
#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
#define PI 3.1415926535897932384626
#define msb(x) (31 - __builtin_clz(x))      
#define msbll(x) (63 - __builtin_clzll(x))  
#define NoSetbitsll(x) __builtin_popcountll(x)
#define setminus(x) memset(x, -1, sizeof(x))
#define setzero(x) memset(x, 0, sizeof(x))
#define f(i, n) for (i = 0; i < n; i++)
#define fe(i,n) for (i = 1; i <=n; i++)
#define fos(i, s, n, k) for (i = s; i < n; i = i + k)
#define fom(i, s, n, k) for (i = s; i < n; i = i * k)
#define uniq(x) (x).erase(unique(all(x)), (x).end())
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());} // for Vector v
#define printPrecision(p, Value) cout << fixed << setprecision(p) << Value
#define tr(it, a) for (auto it = a.begin(); it != a.end(); it++)
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vpi> vvpi;
typedef vector<vpl> vvpl;
typedef vector<bool> vb;

#ifndef ONLINE_JUDGE
#define deb(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define deb(x)
#endif
#pragma warning disable format

//Debugger
void _print(ll t) { cerr << t; }
void _print(int t) { cerr << t; }
void _print(string t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(lld t) { cerr << t; }
void _print(double t) { cerr << t; }
void _print(ull t) { cerr << t; }

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);

template <class T, class V> void _print(pair <T, V> p) { cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}"; }
template <class T> void _print(vector <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(set <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(deque <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(multiset <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T, class V> void _print(map <T, V> v) { cerr << "[ "; for (auto i : v) { _print(i); cerr << " "; } cerr << "]"; }
// template <class T> void _print(ordered_set<T> v) { cerr << "[ "; for (auto i : v) { _print(i); cerr << " "; } cerr << "]"; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll getRandomNumber(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }

ll gcd(ll a, ll b) { if (b > a) { return gcd(b, a); } if (b == 0) { return a; } return gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
ll powm(ll a, ll b, ll mod) { ll res = 1; while (b > 0) { if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1; } return res; }  //power modulo m
void extendgcd(ll a, ll b, ll* v) { if (b == 0) { v[0] = 1; v[1] = 0; v[2] = a; return; } extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return; } //pass an array of size 3
ll mminv(ll a, ll b) { ll arr[3]; extendgcd(a, b, arr); return arr[0]; } //for non prime b
ll mminvprime(ll a, ll b) { if (a % b == 0) return -1; return powm(a, b - 2, b); } //for prime only
vector<ll> sieve(int n) { int* arr = new int[n + 1](); vector<ll> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) { vect.push_back(i); for (int j = i * i; j <= n; j += i)arr[j] = 1; } return vect; }
vector<string> split(string s, char delimeter) { vector <string> tokens; stringstream check1(s); string intermediate; while (getline(check1, intermediate, delimeter)) { tokens.push_back(intermediate); } return tokens; }
string stringRemZeroes(string s) { string res; bool flag = true; for (int i = 0;i < s.length();i++) { if (s[i] == '0' && flag) continue; else { flag = false; res.push_back(s[i]); } } if (res.size() == 0) res = "0"; return res; }
void toLower(string& s) { transform(s.begin(), s.end(), s.begin(), ::tolower); }
void toUpper(string& s) { transform(s.begin(), s.end(), s.begin(), ::toupper); }
ll stringToNo(string s) { stringstream din(s); ll x; din >> x; return x; }
ll addm(ll a, ll b, ll m) { a = a % m; b = b % m; return (((a + b) % m) + m) % m; }
ll mulm(ll a, ll b, ll m) { a = a % m; b = b % m; return (((a * b) % m) + m) % m; }
ll subm(ll a, ll b, ll m) { a = a % m; b = b % m; return (((a - b) % m) + m) % m; }
ll divm(ll a, ll b, ll m) { a = a % m; b = b % m; return (mulm(a, mminvprime(b, m), m) + m) % m; }  //only for prime m
const ll SIZE = 2; // change size before calling
ll fact[SIZE], ifact[SIZE];
void gen_factorial(ll n, ll mod) { fact[0] = fact[1] = ifact[0] = ifact[1] = 1; for (ll i = 2; i <= n; i++) { fact[i] = (i * fact[i - 1]) % mod; } ifact[n] = mminvprime(fact[n], mod); for (ll i = n - 1; i >= 2; i--) { ifact[i] = ((i + 1) * ifact[i + 1]) % mod; } }
ll choose(ll n, ll r, ll m) { ll val1 = fact[n]; ll val2 = ifact[n - r]; ll val3 = ifact[r]; return (((val1 * val2) % m) * val3) % m; } //First make fact and ifact for this to work both ll
//Range intersection
pl intersection(pl a, pl b) { if (a.first > b.second || a.second < b.first) { return mp(-inf, -inf); } else { b.first = max(b.first, a.first); b.second = min(b.second, a.second); } return b; }
pl findRatio(ll a, ll b) { ll g = gcd(a, b); a /= g; b /= g; return mp(a, b); }
template <typename T> void amax(T& a, T b) { a = max(a, b); }
template <typename T> void amin(T& a, T b) { a = min(a, b); }
const int MOD1 = 1000000007;
const int MOD2 = 998244353;
#pragma warning restore format
//**********************************************************TEMPLATE ENDS****************************************************************
/*
THINGS TO KEEP IN MIND BEFORE SUBMITTTING
  * Always Check Which MOD it is Asking For
  * Unique function return iterator Then We can resize the container
  * Look for Possible Edge Cases
  * int overflows, array bounds, etc.
  * https://oeis.org/ Sequence Related Problem
  * a+b=a|b+a&b
  * a+b=a^b+2*(a&b)
  * DO NOT GET STUCK ON ONE APPROACH
  * DO NOT GET STUCK ON ONE APPROACH
  * DO NOT GET STUCK ON ONE APPROACH
*/
#define int long long
int i, j, k;
int n, m;
vector<int> previousSmaller(vector<int>& values)
{
    int n = values.size();
    vector<int> ps(n);
    stack<int> st;
    for (int i = 0;i < n;i++)
    {
        while ((!st.empty()) && (values[st.top()] >= values[i]))
            st.pop();
        ps[i] = (st.empty()) ? -1 : st.top();
        st.push(i);
    }
    return ps;
}
vector<int> nextSmaller(vector<int>& values)
{
    int n = values.size();
    vector<int> ns(n);
    stack<int> st;
    for (i = n - 1;i >= 0;i--)
    {
        while ((!st.empty()) && (values[st.top()] >= values[i]))
            st.pop();
        ns[i] = (st.empty()) ? n : st.top();
        st.push(i);
    }
    return ns;
}
void solve()
{
    int n;
    cin >> n;
    vector<int> pos(n);
    vector<double> radius(n);
    for (int i = 0;i < n;i++)
        cin >> pos[i] >> radius[i];
    vector<double> maxAllowedRadius(n);
    stack<pair<int, double>> st;
    for (int i = 0;i < n;i++)
    {
        double maxRadius = radius[i];
        while (!st.empty())
        {
            pair<int, double> top = st.top();
            amin(maxRadius, ((double((top.first - pos[i]) * (top.first - pos[i]))) / (4 * top.second)));
            if (st.top().second <= maxRadius)
                st.pop();
            else break;
        }
        st.push({ pos[i],maxRadius });
        maxAllowedRadius[i] = maxRadius;
        cout << maxRadius << " ";
    }
    cout << nline;
}

signed main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(3);
    int t = 1;
    // cin >> t;
    int count = 1;
    while (t--) {
        // cout << "Case #" << count << ": ";
        count++;
        solve();
    }
    return 0;
}

Compilation message (stderr)

bal.cpp:57: warning: ignoring '#pragma warning disable' [-Wunknown-pragmas]
   57 | #pragma warning disable format
      | 
bal.cpp:111: warning: ignoring '#pragma warning restore' [-Wunknown-pragmas]
  111 | #pragma warning restore format
      | 
bal.cpp: In function 'std::string stringRemZeroes(std::string)':
bal.cpp:92:83: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 | string stringRemZeroes(string s) { string res; bool flag = true; for (int i = 0;i < s.length();i++) { if (s[i] == '0' && flag) continue; else { flag = false; res.push_back(s[i]); } } if (res.size() == 0) res = "0"; return res; }
      |                                                                                 ~~^~~~~~~~~~~~
bal.cpp: In function 'void gen_factorial(ll, ll)':
bal.cpp:102:117: warning: array subscript 2 is above array bounds of 'll [2]' {aka 'long long int [2]'} [-Warray-bounds]
  102 | void gen_factorial(ll n, ll mod) { fact[0] = fact[1] = ifact[0] = ifact[1] = 1; for (ll i = 2; i <= n; i++) { fact[i] = (i * fact[i - 1]) % mod; } ifact[n] = mminvprime(fact[n], mod); for (ll i = n - 1; i >= 2; i--) { ifact[i] = ((i + 1) * ifact[i + 1]) % mod; } }
      |                                                                                                               ~~~~~~^
bal.cpp:101:4: note: while referencing 'fact'
  101 | ll fact[SIZE], ifact[SIZE];
      |    ^~~~

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