Submission #1262258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262258		user736482	Mixture (BOI20_mixture)	C++20	100 / 100	214 ms	9224 KiB

Mixture

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007 
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
ll n,a,b,c,A,B,C;
map<ld,ll>s[3];
bool czy(pair<ld,ld>x,pair<ld,ld>y){
    return x.ff*y.ss>=x.ss*y.ff;
}
bool check(){
    if(s[0].empty() || s[1].empty())return 0;
    ld p1=(*s[0].begin()).ff;
    ld p2=(*s[1].begin()).ff;
    ld k1=(*--s[0].end()).ff;
    ld k2=(*--s[1].end()).ff;
    //cout<<p1<<" "<<k1<<" "<<p2<<" "<<k2<<" "<<(-k1>p2)<<"\n";
    if(k1<p2 || k2<p1)return 0;
    return 1;
}
pair<ld,ll>gt(ll x,ll y,ll z){
    ll X=__gcd(__gcd(x,y),z);
    //cout<<y<<" "<<X<<" ";
    z/=X;
    x/=X;
    y/=X;
    ll s=C*x-z*A;
    ll d=C*y-z*B;
    ll k=abs(__gcd(s,d));
    if(k){
        s/=k;
        d/=k;
    }
    //cout<<s<<" "<<d<<"g\n";
    if(d==0){
        if(s==0){
            //cout<<x<<" "<<y<<" "<<z<<" "<<A<<" "<<B<<" "<<C<<"\n";
            if(x==A && y==B && z==C)
        return {0,2};
        else return {-1,2};
        }
        return {(ld)INFL,s>0};
    }
    return {(ld)s/(ld)d,(d>0)};
}
pair<ld,ll>x[100007];
ll czy1=0,czy2=0;

void f(pair<ld,ll>co,ll mlt){
    //cout<<co.ff<<" ";
    if(co==pair<ld,ll>{0,2}){
        czy1+=mlt;
        s[co.ss][co.ff]++;
        return;
    }
    czy2+=mlt*s[!co.ss][co.ff];
    if(s[!co.ss][co.ff]==0)s[!co.ss].erase(co.ff);
    s[co.ss][co.ff]++;
}
int main(){
    cin>>A>>B>>C;
    ll X=__gcd(A,__gcd(B,C));
    A/=X;
    B/=X;
    C/=X;
    ll sft=0;
    while(C==0){
        swap(A,B);
        swap(B,C);
        sft++;
    }
    cin>>n;
    ll ak2=1;
    for(ll i=0;i<n;i++){
        char ch;
        cin>>ch;
        if(ch=='A'){
            cin>>a>>b>>c;
            for(ll j=0;j<sft;j++){
                swap(a,b);
                swap(b,c);
            }
            pair<ld,ll>ak=gt(a,b,c);
            x[ak2++]=ak;
            f(ak,1);
            //cout<<ak.ff<<"\n";
        }
        else{
            cin>>a;
            pair<ld,ll>ak=x[(ll)a];
            s[ak.ss][ak.ff]--;
            f(ak,-1);
            s[ak.ss][ak.ff]--;
            if(s[ak.ss][ak.ff]==0)s[ak.ss].erase(ak.ff);
            //cout<<ak.ff<<"\n";
        }
        //cout<<czy2<<" ";
       // cout<<s[0].size()<<" "<<s[1].size()<<"\n";
        if(czy1)cout<<1;
        else if(czy2)cout<<2;
        else if(check())cout<<3;
        else cout<<0;
        cout<<"\n";
    }
}

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