Cod sursa(job #2542185)

Utilizator NashikAndrei Feodorov Nashik Data 9 februarie 2020 17:45:33
Problema Pachete Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb
//#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("pachete.in");
ofstream cout("pachete.out");
multiset <int> se;
pair<int,int> v[50005];
vector<int>c1,c2,c3,c4;
bool mysort(int a,int b){
    return v[a].first<v[b].first;
}
int sol,n,p,q;
int ok;
bool valid(int cate){
    //cout<<cate<<"\n";
    se.clear();
    int nn;
    for(int i=1;i<=cate;i++)
        se.insert(0);
    if(ok==1){
        nn=c1.size();
    }
    if(ok==2){
        nn=c2.size();
    }
    if(ok==3){
        nn=c3.size();
    }
    if(ok==4){
        nn=c4.size();
    }
    for(int i=0;i<nn;i++){
        multiset<int>::iterator it;
        int x;
        if(ok==1){
            it=se.upper_bound(v[c1[i]].second);
            x=v[c1[i]].second;
        }
        if(ok==2){
            it=se.upper_bound(v[c2[i]].second);
            x=v[c2[i]].second;
        }
        if(ok==3){
            it=se.upper_bound(v[c3[i]].second);
            x=v[c3[i]].second;
        }
        if(ok==4){
            it=se.upper_bound(v[c4[i]].second);
            x=v[c4[i]].second;
        }
        if(it==se.begin())
            return false;
        it--;
        if((*it)>x){
            return false;
        }
        /*if(it==se.end()){
            return false;
        }
        */
        se.erase(it);
        se.insert(x);
    }
    return true;
}
void cb(int st,int dr){
    //cout<<st<<" "<<dr<<"\n";
    if(st>dr)
        return;
    int mid=(st+dr)/2;
    //cout<<mid<<"\n";
    if(valid(mid)==true){
        sol=mid;
        cb(st,mid-1);
    }else{
        cb(mid+1,dr);
    }
}
int main()
{
    int a,b;
    cin>>n;
    cin>>p>>q;
    for(int i=1;i<=n;i++){
         cin>>a>>b;
         if(a>p and b>q){
            c1.push_back(i);
         }
         if(a>p and b<q){
            c2.push_back(i);
            b+=(q-b)*2;
         }
         if(a<p and b>q){
            c3.push_back(i);
            a+=(p-a)*2;
         }
         if(a<p and b<q){
            c4.push_back(i);
            b+=(q-b)/2;
            a+=(p-a)*2;
         }
         v[i].first=a;
         v[i].second=b;
    }
    sort(c1.begin(),c1.end(),mysort);
    sort(c2.begin(),c2.end(),mysort);
    sort(c3.begin(),c3.end(),mysort);
    sort(c4.begin(),c4.end(),mysort);
    int suma=0;
    ok=1;
    cb(0,n);
    suma+=sol;
    ok=2;
    //cout<<sol<<"\n";
    cb(0,n);
    suma+=sol;
    ok=3;
    //cout<<sol<<"\n";
    cb(0,n);
    suma+=sol;
    //cout<<sol<<"\n";
    ok=4;
    cb(0,n);
    suma+=sol;
    //cout<<sol<<"\n";
    cout<<suma;
    return 0;
}