Submission #793109

#TimeUsernameProblemLanguageResultExecution timeMemory
793109AmylopectinRoads (CEOI20_roads)C++14
100 / 100
161 ms19908 KiB
#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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...