Submission #793109

#	Time	Username	Problem	Language	Result	Execution time	Memory
793109		Amylopectin	Roads (CEOI20_roads)	C++14	100 / 100	161 ms	19908 KiB

roads

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
const long long mxn = 1e6 + 10,mxi = 2e7 + 10;
double cxx;
struct sett
{
    double stx,sty,slo;
    long long num;
    bool operator () (const struct sett &l,const struct sett &r)const
    {
        return (l.sty + (cxx - l.stx) * l.slo) < (r.sty + (cxx - r.stx) * r.slo);
        // return l.sty > r.sty;
    }
};

struct we
{
    long long xx,yy,sta,num,bey;
    double slo,soo;
};
bool cmp(const struct we &l,const struct we &r)
{
    // if(l.soo - r.soo > 0.0000001 || l.soo - r.soo < -0.0000001)
    // // if(l.soo != r.soo)
    //     return l.soo < r.soo;
    if(l.xx != r.xx)
        return l.xx < r.xx;
    return l.yy < r.yy;
}
set<struct sett,struct sett> see;
struct we ta[mxn] = {};
long long nux[mxn] = {},nuy[mxn] = {};
int main()
{
    long long i,j,n,m,cn,cm,fn,fm,f,sta = 0,of;
    set<struct sett>::iterator cit,fit;
    double t,p,cslo,cx,cy;
    scanf("%lld",&n);
    for(i=0; i<n; i++)
    {
        scanf("%lld %lld %lld %lld",&cn,&cm,&fn,&fm);
        if(cn > fn || (cn == fn && cm > fm))
        {
            f = cn;
            cn = fn;
            fn = f;
            f = cm;
            cm = fm;
            fm = f;
        }
        if(fn - cn == 0)
        {
            // sta = 1;
            cslo = mxi;
            // cslo = mxi;
        }
        else 
        {
            t = fm - cm;
            p = fn - cn;
            // ta[i].slo = t / p;
            cslo = t/p;
        }
        ta[i*2] = {cn,cm,0,i,0,cslo,0};
        ta[i*2+1] = {fn,fm,1,i,cm,cslo,0};
    }
    sort(ta,ta+n*2,cmp);
    see.insert({-mxi,-mxi,0,n});
    of = 0;
    printf("\n");
    for(i=0; i<2*n; i++)
    {
        cxx = ta[i].xx;
        cx = cxx;
        cy = ta[i].yy;
        if(ta[i].sta == 0)
        {
            cn = (*prev(see.upper_bound({cx,cy,0,0}))).num;
            if(cn == n && of == 0)
            {
                of = 1;
            }
            else 
            {
                printf("%lld %lld %.0lf %.0lf\n",nux[cn],nuy[cn],cx,cy);
            }
            nux[cn] = cx;
            nuy[cn] = cy;
            see.insert({cx,cy,ta[i].slo,ta[i].num});
            fn = ta[i].num;
            nux[fn] = cx;
            nuy[fn] = cy;
        }
        else 
        {
            cit = prev(see.upper_bound({cx,cy+0.001,0,0}));
            // cn = (*cit).num;
            fit = prev(cit);
            cn = (*fit).num;
            see.erase(cit);
            nux[cn] = cx;
            nuy[cn] = cy;
        }
    }
    // if(sta == 1)
    // {
    //     for(i=0; i<n; i++)
    //     {
    //         ta[i].soo = ta[i].xx;
    //     }
    // }
    // else 
    // {
    //     for(i=0; i<n; i++)
    //     {
    //         t = ta[i].xx;
    //         f = ta[i].yy;
    //         ta[i].soo = f - (t * cslo);
    //     }
    // }
    // sort(ta,ta+n,cmp);
    // printf("\n");
    // for(i=0; i<n-1; i++)
    // {
    //     // if(ta[i].soo != ta[i+1].soo)
    //     // {
    //     //     printf("%lld %lld %lld %lld\n",ta[i].xx,ta[i].yy,ta[i+1].xx,ta[i+1].yy);
    //     // }
    //     // else 
    //     // {
    //         printf("%lld %lld %lld %lld\n",ta[i].xx2,ta[i].yy2,ta[i+1].xx,ta[i+1].yy);
    //     // }
    // }
    return 0;
}

Compilation message (stderr)

roads.cpp: In function 'int main()':
roads.cpp:39:17: warning: unused variable 'j' [-Wunused-variable]
   39 |     long long i,j,n,m,cn,cm,fn,fm,f,sta = 0,of;
      |                 ^
roads.cpp:39:21: warning: unused variable 'm' [-Wunused-variable]
   39 |     long long i,j,n,m,cn,cm,fn,fm,f,sta = 0,of;
      |                     ^
roads.cpp:39:37: warning: unused variable 'sta' [-Wunused-variable]
   39 |     long long i,j,n,m,cn,cm,fn,fm,f,sta = 0,of;
      |                                     ^~~
roads.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
roads.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%lld %lld %lld %lld",&cn,&cm,&fn,&fm);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 40 / 40