Submission #1262280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262280		Zbyszek99	Mixture (BOI20_mixture)	C++20	100 / 100	534 ms	40136 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 long 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;
    int ind = -1;
    bool operator<(const point& other) const
    {
        if(ind > 0) return ind < other.ind;
        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;
            }
            return (abs(x)+abs(y))>(abs(other.x)+abs(other.y));
        }
    }
};

bool is180(point p1, point p2)
{
    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];
int cur = 1;
multiset<point> sort_points;
map<pair<ld,ld>,int> point_cnt;
int rel_ind[100001];

void add(ld x, ld y, int c)
{
    int type = 0;
    if((x == 0 && y <= 0) || x > 0) type = 1;
    ld p = round(x/y*1e12);
    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,c});
        cnt_180++;
    }
    else
    {
        auto nxt = sort_points.upper_bound({x,y,c});
        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,c};
        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, int c)
{
    int type = 0;
    if((x == 0 && y <= 0) || x > 0) type = 1;
    ld p = round(x/y*1e12);
    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}]--;
    if(siz(sort_points) == 1)
    {
        sort_points.erase(sort_points.find({x,y,c}));
        cnt_180--;
    }
    else
    {
        sort_points.erase(sort_points.find({x,y,c}));
        auto nxt = sort_points.upper_bound({x,y,c});
        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,c};
        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;
    vector<pair<char,int>> opers;
    rep(i,n)
    {
        char z;
        cin >> z;  
        if(z == 'A')
        {
            ld x,y,z;
            cin >> x >> y >> z;
            opers.pb({'A',-1});
            rep(i,cyc)
            {
                swap(z,y);
                swap(y,x);
            }
            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;
                x -= x1;
                y -= y1;
            }
            add(x,y,-cur);
            points[cur++] = {x,y};
        }
        else
        {
            int x;
            cin >> x;
            opers.pb({'R',x});
        }
    }
    int p = 1;
    forall(it,sort_points)
    {
        rel_ind[-it.ind] = p++;
    }
    lines_cnt = 0;
    cnt_180 = 0;
    dif_lines = {};
    rep(d,2) lines[d] = {};
    point_cnt = {};
    sort_points = {};
    cur = 1;
    forall(it,opers)
    {
        if(it.ff == 'A')
        {
            add(points[cur].ff,points[cur].ss,rel_ind[cur]);
            cur++;
        }
        else
        {
            del(points[it.ss].ff,points[it.ss].ss,rel_ind[it.ss]);
        }
        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: 40 / 40