제출 #773429

#제출 시각아이디문제언어결과실행 시간메모리
773429AmylopectinAliens (IOI16_aliens)C++14
4 / 100
1 ms352 KiB
#include "aliens.h" #include <stdio.h> #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; const long long mxn = 1e6 + 10; struct pri { long long fi,se,are; bool operator () (const struct pri &l,const struct pri &r) { return l.are > r.are; } }; struct we { long long dip,hei; }; bool cmp(const struct we &l,const struct we &r) { return l.dip < r.dip; } priority_queue <struct pri, vector<struct pri>, struct pri> qu; struct we sot[mxn] = {},ta[mxn] = {}; long long sem[mxn] = {},u[mxn] = {},le[mxn] = {},ri[mxn] = {},leva[mxn] = {} ,riva[mxn] = {}; long long ab(long long l) { if(l < 0) return -l; return l; } long long squ(long long l) { return l*l; } // long long bui(long long cl,long long cr,long long no) // { // if(cl == cr) // { // sem[i] = 1; // return 0; // } // long long mid = (cl+cr) / 2; // bui(cl,mid,no*2); // bui(mid+1,cr,no*2+1); // sem[no] = sem[no*2] + sem[no*2+1]; // return 0; // } long long take_photos(int nn, int mm, int nnph , std::vector<int> rr, std::vector<int> cc) { long long n = nn,m = mm, nph = nnph,i,j,k,cn,cm,fn,fm ,ru = 0,su = 0,care,fdip,fhei,cva,cfi,cse,ffi,fse,cl,cr; for(i=0; i<n; i++) { rr[i] ++; cc[i] ++; if(rr[i] > cc[i]) { cn = rr[i]; rr[i] = cc[i]; cc[i] = cn; } sot[i] = {rr[i] + cc[i] - 1,cc[i] - rr[i]}; } sort(sot,sot+n,cmp); ta[0] = {sot[0].dip,sot[0].hei}; ru = 0; for(i=1; i<n; i++) { while(ru >= 0 && ta[ru].dip - ta[ru].hei >= sot[i].dip - sot[i].hei) { ru--; } if(ta[ru].dip + ta[ru].hei < sot[i].dip + sot[i].hei) { ru++; ta[ru] = {sot[i].dip,sot[i].hei}; } } su += squ((ta[0].hei+1)); le[0] = -1; ri[ru] = -1; for(i=1; i<=ru; i++) { cn = ta[i-1].dip + ta[i-1].hei; cm = ta[i].dip - ta[i].hei; if(cn >= cm) { fn = (cn-cm+2)/2; su -= squ(fn); cva = (ta[i-1].hei+1-fn) * (ta[i].hei+1-fn) * 2; qu.push({i-1,i,cva}); } else { fn = ((ta[i].dip + ta[i].hei) - (ta[i-1].dip - ta[i-1].hei) + 2)/2; cva = squ(fn) - squ(ta[i-1].hei+1) - squ(ta[i].hei+1); qu.push({i-1,i,cva}); } su += squ((ta[i].hei+1)); leva[i] = cva; riva[i-1] = cva; ri[i-1] = i; le[i] = i-1; } // bui(0,ru,1); for(i=0; i<=ru-nph; i++) { while(!qu.empty()) { cfi = qu.top().fi; cse = qu.top().se; care = qu.top().are; qu.pop(); if(u[cfi] != 0 || u[cse] != 0 || leva[cse] != care || riva[cfi] != care) { continue; } break; } su += care; fse = (ta[cse].dip + ta[cse].hei); ffi = ta[cfi].dip - ta[cfi].hei; fdip = (ffi+fse) / 2; fhei = (fse-ffi) / 2; ta[cfi].dip = fdip; ta[cfi].hei = fhei; u[cse] = 1; cl = le[cfi]; cr = ri[cse]; if(cl != -1) { cn = ta[cl].dip + ta[cl].hei; cm = fdip - fhei; if(cn >= cm) { fn = (cn-cm+2)/2; // su -= squ(fn); cva = (ta[cl].hei+1-fn) * (fhei+1-fn) * 2; qu.push({cl,cfi,cva}); } else { fn = ((fdip + fhei) - (ta[cl].dip - ta[cl].hei) + 2)/2; cva = squ(fn) - squ(ta[cl].hei+1) - squ(fhei+1); qu.push({cl,cfi,cva}); } leva[cfi] = cva; riva[cl] = cva; } if(cr != -1) { cn = fdip + fhei; cm = ta[cr].dip - ta[cr].hei; if(cn >= cm) { fn = (cn-cm+2)/2; // su -= squ(fn); cva = (fhei+1-fn) * (ta[cr].hei+1-fn) * 2; qu.push({cfi,cr,cva}); } else { fn = ((ta[cr].dip + ta[cr].hei) - (fdip - fhei) + 2)/2; cva = squ(fn) - squ(fhei+1) - squ(ta[cr].hei+1); qu.push({cfi,cr,cva}); } leva[cr] = cva; riva[cfi] = cva; le[cr] = cfi; ri[cfi] = cr; } else { ri[cfi] = -1; } } return su; }

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:56:22: warning: unused variable 'm' [-Wunused-variable]
   56 |     long long n = nn,m = mm, nph = nnph,i,j,k,cn,cm,fn,fm
      |                      ^
aliens.cpp:56:43: warning: unused variable 'j' [-Wunused-variable]
   56 |     long long n = nn,m = mm, nph = nnph,i,j,k,cn,cm,fn,fm
      |                                           ^
aliens.cpp:56:45: warning: unused variable 'k' [-Wunused-variable]
   56 |     long long n = nn,m = mm, nph = nnph,i,j,k,cn,cm,fn,fm
      |                                             ^
aliens.cpp:56:56: warning: unused variable 'fm' [-Wunused-variable]
   56 |     long long n = nn,m = mm, nph = nnph,i,j,k,cn,cm,fn,fm
      |                                                        ^~
aliens.cpp:127:38: warning: 'cse' may be used uninitialized in this function [-Wmaybe-uninitialized]
  127 |         fse = (ta[cse].dip + ta[cse].hei);
      |                              ~~~~~~~~^~~
aliens.cpp:128:37: warning: 'cfi' may be used uninitialized in this function [-Wmaybe-uninitialized]
  128 |         ffi = ta[cfi].dip - ta[cfi].hei;
      |                             ~~~~~~~~^~~
aliens.cpp:126:12: warning: 'care' may be used uninitialized in this function [-Wmaybe-uninitialized]
  126 |         su += care;
      |         ~~~^~~~~~~
#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...