oj.uz

Submission #256558

# Submission time Handle Problem Language Result Execution time Memory
256558 2020-08-02T20:48:24 Z davitmarg Mixture (BOI20_mixture) C++17
30 / 100
 17 ms 896 KB 
/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;

const int N = 200005;

LD X, Y, Z, pi = 3.1415926535897932384626433832795028841971, eps = 10e-15;
vector<LD> vx, vy;
multiset<pair<LD, LD>> s;
multiset<LD> sa, mx;
int n, ans2;

LD getAng(LD x, LD y)
{
    LD d = sqrtl(x * x + y * y);
    LD e = acos(x / d);
    assert(d != 0);
    if (y < 0)
        e = pi + pi - e;
    return e;
}

LD inv(LD e)
{
    if (e >= pi)
        return e - pi;
    return e + pi;
}

bool fnd(LD e)
{
    auto it = sa.lower_bound(e - eps);
    return (it != sa.end() && *it <= e + eps);
}

void add(LD e)
{
    sa.insert(e);
    if (sa.size() == 1)
        return;
    auto it = sa.find(e);

    LD lst, nxt;
    bool inv = 0;

    if (it == sa.begin())
    {
        ++it;
        mx.insert(*it - e);
        return;
    }
    else
    {
        it--;
        lst = *it;
        it++;
    }
    it++;

    if (it == sa.end())
    {
        it--;
        it--;
        mx.insert(e - *it);
        return;
    }
    else
        nxt = *it;
    mx.erase(mx.lower_bound(abs(nxt - lst) - eps));
    mx.insert(abs(e - lst));
    mx.insert(abs(e - nxt));
}


void rem(LD e)
{

    if (sa.size() == 1)
    {
        sa.clear();
        return;
    }
    auto it = sa.lower_bound(e - eps);
    e = *it;

    LD lst, nxt;
    bool inv = 0;

    if (it == sa.begin())
    {
        ++it;
        mx.erase(mx.lower_bound(*it - e - eps));
        sa.erase(sa.find(e));
        return;
    }
    else
    {
        it--;
        lst = *it;
        it++;
    }
    it++;

    if (it == sa.end())
    {
        it--;
        mx.erase(mx.lower_bound(e - *it - eps));
        sa.erase(sa.find(e));
        return;
    }
    else
        nxt = *it;
    mx.insert(abs(nxt - lst));
    mx.erase(mx.lower_bound(e - lst - eps));
    mx.erase(mx.lower_bound(nxt - e - eps));
    sa.erase(sa.find(e));
}

LD get()
{
    if (mx.empty())
        return pi + pi;
    LD res = 0;
    if (sa.size() > 1)
    {
        LD e = (*sa.rbegin() - *sa.begin());
        res = pi + pi - e;
    }
    return max(res, *mx.rbegin());
}

void add(LD x, LD y)
{
    s.insert(MP(x, y));
    if (abs(x) > eps || abs(y) > eps)
    {
        LD e = getAng(x, y);
        if (!fnd(e) && fnd(inv(e)))
            ans2++;
        add(e);
    }
}


void rem(LD x, LD y)
{
    s.erase(s.find(MP(x, y)));
    if (abs(x) > eps || abs(y) > eps)
    {
        LD e = getAng(x, y);
        rem(e);
        if (!fnd(e) && fnd(inv(e)))
            ans2--;
    }
}

int main()
{
    fastIO;
    cin >> Z >> Y >> X;
    Z += X + Y;
    cin >> n;
    /*X /= Z;
    Y /= Z;*/
    vx.push_back(0);
    vy.push_back(0);
    while (n--)
    {
        char c;
        cin >> c;
        if (c == 'A')
        {
            LD x, y, z;
            cin >> z >> y >> x;
            z += x + y;
            x *= Z / z;
            y *= Z / z;
            x -= X;
            y -= Y;
            if (sqrtl(x*x+y*y) <= eps)
            {
                x = 0;
                y = 0;
            }
            vx.push_back(x);
            vy.push_back(y);
            add(x, y);
        }
        else
        {
            int p;
            cin >> p;
            rem(vx[p], vy[p]);
        }

        if (s.find(MP(0, 0)) != s.end())
            cout << 1 << endl;
        else if (ans2)
            cout << 2 << endl;
        else if (get() <= pi + eps)
            cout << 3 << endl;
        else
            cout << 0 << endl;
    }

    return 0;
}

/*


*/

Compilation message

Mixture.cpp: In function 'void add(long double)':
Mixture.cpp:71:10: warning: unused variable 'inv' [-Wunused-variable]
     bool inv = 0;
          ^~~
Mixture.cpp: In function 'void rem(long double)':
Mixture.cpp:114:10: warning: unused variable 'inv' [-Wunused-variable]
     bool inv = 0;
          ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 288 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 288 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 2 ms 384 KB Output is correct
34 Correct 3 ms 384 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 3 ms 384 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 288 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 2 ms 384 KB Output is correct
34 Correct 3 ms 384 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 3 ms 384 KB Output is correct
37 Correct 4 ms 384 KB Output is correct
38 Correct 3 ms 384 KB Output is correct
39 Correct 6 ms 512 KB Output is correct
40 Correct 4 ms 512 KB Output is correct
41 Correct 5 ms 512 KB Output is correct
42 Correct 4 ms 512 KB Output is correct
43 Correct 5 ms 512 KB Output is correct
44 Correct 5 ms 512 KB Output is correct
45 Correct 6 ms 512 KB Output is correct
46 Correct 16 ms 896 KB Output is correct
47 Correct 17 ms 896 KB Output is correct
48 Incorrect 9 ms 512 KB Output isn't correct
49 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 288 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 2 ms 384 KB Output is correct
34 Correct 3 ms 384 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 3 ms 384 KB Output is correct
37 Correct 4 ms 384 KB Output is correct
38 Correct 3 ms 384 KB Output is correct
39 Correct 6 ms 512 KB Output is correct
40 Correct 4 ms 512 KB Output is correct
41 Correct 5 ms 512 KB Output is correct
42 Correct 4 ms 512 KB Output is correct
43 Correct 5 ms 512 KB Output is correct
44 Correct 5 ms 512 KB Output is correct
45 Correct 6 ms 512 KB Output is correct
46 Correct 16 ms 896 KB Output is correct
47 Correct 17 ms 896 KB Output is correct
48 Incorrect 9 ms 512 KB Output isn't correct
49 Halted 0 ms 0 KB -