Submission #1262271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262271		Zbyszek99	Mixture (BOI20_mixture)	C++20	60 / 100	6 ms	1096 KiB

Mixture

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

struct point
{
    ld x,y;
    bool operator<(const point& other) const
    {
     //   cout << x << " " << y << " " << other.x << " " << other.y << " por\n";
        if(x == 0 && y == 0) return 0;
        if(other.x == 0 && other.y == 0) return 1;
        if(x == other.x && y == other.y) return 0;
        int d1 = y > 0;
        int d2 = other.y > 0;
        if(d1 != d2)
        {
            if(y <= 0) return 0;
            return 1;
        }
        if(x*other.y-other.x*y != 0)
        {
            return x*other.y-other.x*y < 0;
        }
        else
        {
            int d1 = y > 0;
            int d2 = other.y > 0;
            if(d1 != d2)
            {
                if(y > 0) return 0;
                return 1;
            }
            if(y == other.y && y == 0)
            {
                return x>other.x;
            }
            if((abs(x)+abs(y))!=(abs(other.x)+abs(other.y)))
            {
                return (abs(x)+abs(y))<(abs(other.x)+abs(other.y));
            }
            return 0;
        }
    }
};

bool is180(point p1, point p2)
{
   // cerr << p1.x << " " << p1.y << " " << p2.x << " " << p2.y << "    " << p1.x*p2.y-p2.x*p1.y << "        is180\n";
    return p1.x*p2.y-p2.x*p1.y>0;
}

map<ld,int> lines[2];
set<ld> dif_lines;
int lines_cnt;
int cnt_180;
pair<ld,ld> points[100001];
bool is_del[100001];
int cur = 1;
multiset<point> sort_points;
map<pair<ld,ld>,int> point_cnt;

void add(ld x, ld y)
{
    int type = 0;
    if((x == 0 && y <= 0) || x > 0) type = 1;
    ld p = round(x/y*1e9);
    dif_lines.insert(p);
    if(y == 0) p = -1;
    lines[type][p]++;
    if(lines[type][p] == 1 && lines[type^1][p] >= 1) lines_cnt++;
    point_cnt[{x,y}]++;
    if(siz(sort_points) == 0)
    {
        sort_points.insert({x,y});
        cnt_180++;
    }
    else
    {
        auto nxt = sort_points.upper_bound({x,y});
        point nx;
        if(nxt == sort_points.end())
        {
            nx = *(sort_points.begin());
        }
        else
        {
            nx = *nxt;
        }
        point pv;
        if(nxt != sort_points.begin())
        {
            nxt--;
            pv = *nxt;
        }
        else
        {
            pv = *(--sort_points.end());
        }
        point p = {x,y};
        if(is180(pv,nx) || siz(sort_points) == 1) cnt_180--;
        if(is180(pv,p)) cnt_180++;
        if(is180(p,nx)) cnt_180++;
        sort_points.insert(p);
    }
}

void del(ld x, ld y)
{
   // cout << x << " " << y << " del\n";
    int type = 0;
    if((x == 0 && y <= 0) || x > 0) type = 1;
    
    ld p = round(x/y*1e9);
    if(y == 0) p = -1;
    if(lines[type][p] == 1 && lines[type^1][p] >= 1) lines_cnt--;
    lines[type][p]--;
    if(lines[type][p]+lines[type^1][p] == 0) dif_lines.erase(p);
    point_cnt[{x,y}]--;
   // cout << "xd\n";
    if(siz(sort_points) == 1)
    {
        sort_points.erase(sort_points.find({x,y}));
        cnt_180--;
    }
    else
    {
        // cout << " dupa\n";
        // point pom = {x,y};
        // forall(it,sort_points) 
        // {
        //    cout << it.x << " " << it.y << "haha\n";
        //     cout << it.x << " " << it.y << " xd:   " << (pom<it) << " " << (it<pom) << " it\n";
        // }
        // cout << "dupa\n";
        // if(sort_points.find({x,y}) == sort_points.end()) cout << " no no\n";
         sort_points.erase(sort_points.find({x,y}));
       //cout << "xd\n";
        auto nxt = sort_points.upper_bound({x,y});
        point nx;
        if(nxt == sort_points.end())
        {
            nx = *(sort_points.begin());
        }
        else
        {
            nx = *nxt;
        }
        point pv;
        if(nxt != sort_points.begin())
        {
            nxt--;
            pv = *nxt;
        }
        else
        {
            pv = *(--sort_points.end());
        }
        point p = {x,y};
        if(is180(pv,nx) || siz(sort_points) == 1) cnt_180++;
        if(is180(pv,p)) cnt_180--;
        if(is180(p,nx)) cnt_180--;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    ld x1,y1,z1;
    cin >> x1 >> y1 >> z1;
    int cyc = 0;
    while(z1 == 0)
    {
        cyc++;
        swap(z1,y1);
        swap(y1,x1);
    }
    bool is_zero = (z1 == 0);
    if(x1 != 0 || y1 != 0)
    {
        ll g = __gcd((ll)x1,(ll)y1);
        x1 /= g;
        y1 /= g;
        z1 /= g;
    }
    if(!is_zero)
    {
        x1 /= z1;
        y1 /= z1;
    }
    int n;
    cin >> n;
    rep(i,n)
    {
        char z;
        cin >> z;     
        if(z == 'A')
        {
            ld x,y,z;
            cin >> x >> y >> z;
            rep(i,cyc)
            {
                swap(z,y);
                swap(y,x);
            }
            if(!is_zero)
            {
                if(x != 0 && y != 0)
                {
                    ll g = __gcd((ll)x,(ll)y);
                    x /= g;
                    y /= g;
                    z /= g;
                }
                if(z != 0)
                {
                    x /= z;
                    y /= z;
                    //cout << x << " " << y  << " " << x/y << " xy\n";
                    x -= x1;
                    y -= y1;
                }
           //     cout << x << " " << y  << " " << x/y << " xy\n";
                add(x,y);
                points[cur++] = {x,y};
            }
            else
            {
                if(z == 0)
                {
                   ll g = __gcd((ll)x,(ll)y);
                    x /= g;
                    y /= g;
                    x -= x1;
                    y -= y1;
            //      //cout << x << " " << y  << " " << x/y << " xy\n";
                    add(x,y);
                    points[cur++] = {x,y};
                        
                }
                else
                {
                    is_del[cur] = 1;
                    cur++;
                }
            }
        }
        else
        {
            int x;
            cin >> x;
            if(!is_del[x])
            {
                del(points[x].ff,points[x].ss);
            }
        }
        // if(i == 1633)
        // {
        //     cout << cnt_180 << " cnt\n";
        //     forall(it,sort_points)
        //     {
        //         cout << it.x << " " << it.y << " points\n";
        //     }
        //     if(point_cnt[{0,0}]) cout << "1\n";
        // else if(lines_cnt > 0) cout << "2\n";
        // else if(cnt_180 == 0 && siz(sort_points) > 2 && siz(dif_lines) > 1) cout << "3\n";
        // else cout << "0\n";
        // }
        if(point_cnt[{0,0}]) cout << "1\n";
        else if(lines_cnt > 0) cout << "2\n";
        else if(cnt_180 == 0 && siz(sort_points) > 2 && siz(dif_lines) > 1) cout << "3\n";
        else cout << "0\n";
    }
}

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40