제출 #1100130

#제출 시각아이디문제언어결과실행 시간메모리
1100130fve5Naval battle (CEOI24_battle)C++17
76 / 100
3080 ms593988 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #include <bits/extc++.h> #include <unistd.h> #include <fcntl.h> using namespace std; using namespace __gnu_pbds; template<size_t BUFSIZE=1<<16> class Scanner{ private: char buf[BUFSIZE]; char* it; char* ed; const int fd; Scanner(const Scanner&) = delete; Scanner& operator=(const Scanner&) = delete; void flush(){ if(it==ed){ ed=buf+read(fd,buf,BUFSIZE); it=buf; } } void ss(){ flush(); while(*it<=32){++it;flush();} } void scan(char& x){ss();x=*(it++);} void scan(string& x){ do{ ss(); char * itbg=it; while(it!=ed&&*it>32)++it; x.append(itbg,it); } while(it==ed); } template<typename T> void scan_u(T& x){ ss(); x=0; do{ x=T(x*10+*(it++)-'0'); flush(); } while(*it>32); } template<typename T> void scan_i(T& x){ ss(); x=0; bool sign=0; if(*it=='-'){ sign=1; ++it; flush(); } do{ x=T(x*10+*(it++)-'0'); flush(); } while(*it>32); if(sign)x=T(-x); } template<typename T> void scan_f(T& x){ ss(); x=0; bool sign=0; if(*it=='-'){ sign=1; ++it; flush(); } while(*it>32 && *it!='.'){ x=x*T(10.0)+T(*(it++)-'0'); flush(); } if(*it=='.'){ ++it; flush(); T e=T(0.1); while(*it>32){ x=x+e*T(*(it++)-'0'); e=e*T(0.1); flush(); }; } if(sign)x=-x; } void scan(int8_t& x){scan_i(x);} void scan(int16_t& x){scan_i(x);} void scan(int32_t& x){scan_i(x);} void scan(int64_t& x){scan_i(x);} void scan(long long& x){scan_i(x);} void scan(uint8_t& x){scan_u(x);} void scan(uint16_t& x){scan_u(x);} void scan(uint32_t& x){scan_u(x);} void scan(uint64_t& x){scan_u(x);} void scan(unsigned long long& x){scan_u(x);} void scan(float& x){double d; scan_f(d); x=d;} void scan(double& x){scan_f(x);} void scan(long double& x){scan_f(x);} template<typename T> void scan(T& x){for(auto &i:x)scan(i);} public: ~Scanner(){} Scanner(const int _fd=0):it(0),ed(0),fd(_fd){} void operator()(){} template<typename T, typename...R> void operator()(T& a,R&...rest){ scan(a); operator()(rest...); } }; template<size_t BUFSIZE=1<<16> class Printer { private: char buf[BUFSIZE]; char* it; const int fd; void fif(const size_t x){ if(size_t(BUFSIZE+buf-it)<x)flush(); } void print(const char x){fif(1);*(it++)=x;} void print(char* const x){ size_t s = strlen(x); if(s>BUFSIZE/2){ flush(); write(fd,x,s); } else { fif(s); copy(x,x+s,it); it+=s; } } void print(const char* const x){print((char*)x);} void print(const string& x){ if(x.size()>BUFSIZE/2){ flush(); write(fd,x.data(),x.size()); } else { fif(x.size()); copy(x.begin(),x.end(),it); it+=x.size(); } } template<typename T> void print_u(T x){ constexpr size_t siz = size_t(sizeof(T) * log10(256)) + 1; uint8_t i=siz; char b[siz]; do { b[--i]=char(x%10+'0'); x=T(x/10); }while(x); fif(siz-i); copy(b+i,b+siz,it); it+=siz-i; } template<typename T> void print_i(T x){ constexpr size_t siz = size_t(sizeof(T) * log10(256)) + 2; size_t i=siz; char b[siz]; const bool neg=(x<0); if(neg)x=-x; do { b[--i]=char(x%10+'0'); x=T(x/10); }while(x); if(neg)b[--i]='-'; fif(siz-i); copy(b+i,b+siz,it); it+=siz-i; } void print_f(const double x){ const uint64_t d = *((uint64_t*)&x); const bool neg = d>>63; int32_t e = (d>>52)&((1ull<<11)-1); uint64_t m = d&((1ull<<52)-1); if(e){ e-=1075; m+=(1ull<<52); } else e=-1074ll; int32_t re=e; if(e<0){ while(e++){ if(m&0xe000000000000000){ m>>=1; re++; } else m*=5; } } else { while(e--){ if(m&0x8000000000000000) m/=5; else { m<<=1; re--; } } } if(neg)print('-'); print(m); print('e'); print(re); } void print(int8_t x){print_i(x);} void print(int16_t x){print_i(x);} void print(int32_t x){print_i(x);} void print(int64_t x){print_i(x);} void print(long long x){print_i(x);} void print(uint8_t x){print_u(x);} void print(uint16_t x){print_u(x);} void print(uint32_t x){print_u(x);} void print(uint64_t x){print_u(x);} void print(unsigned long long x){print_u(x);} void print(const float x){print_f(x);} void print(const double x){print_f(x);} void print(const long double x){print_f(x);} template<typename T> void print(const T& x){ for(auto &i:x){ print(i); print(' '); } } public: ~Printer(){flush();} Printer(const int _fd=1):it(buf),fd(_fd){} void flush(){ write(fd,buf,it-buf); it=buf; } void operator()(){} template<typename T, typename...R> void operator()(T&& a,R&&...rest){ print(a); operator()(rest...); } }; struct Ship { int x, y; char dir; int dist(const Ship &o) const { return abs(x - o.x) + abs(y - o.y); } }; enum { N, E, S, W }; int dir_num(char dir) { switch (dir) { case 'N': return N; case 'E': return E; case 'S': return S; case 'W': return W; } } #define LEFT(dir, card, repr, discr) \ it = (dir)[card][repr].lower_bound(discr); \ if (it != (dir)[card][repr].begin() && !(dir)[card][repr].empty()) \ add_crash(ship, prev(it)->second); #define RIGHT(dir, card, repr, discr) \ it = (dir)[card][repr].upper_bound(discr); \ if (it != (dir)[card][repr].end()) \ add_crash(ship, it->second); Scanner<> scan; Printer<> prnt; int main() { int n; scan(n); vector<Ship> ships(n); for (auto &[x, y, dir]: ships) scan(x, y, dir); gp_hash_table<int, map<int, int>> hor[4], ver[4], diagp[4], diagm[4]; for (int i = 0; i < n; i++) { auto [x, y, dir] = ships[i]; int d = dir_num(dir); hor[d][y][x] = i; ver[d][x][y] = i; diagp[d][x + y][x] = i; diagm[d][x - y][x] = i; } map<int, vector<pair<int, int>>> crashes; auto add_crash = [&](int u, int v) { crashes[ships[u].dist(ships[v])].emplace_back(u, v); }; auto next_crash = [&](int ship) { auto [x, y, dir] = ships[ship]; vector<int> crashes; map<int, int>::iterator it; switch (dir) { case 'N': LEFT(ver, S, x, y); LEFT(diagm, E, x - y, x); RIGHT(diagp, W, x + y, x); return; case 'E': RIGHT(hor, W, y, x); RIGHT(diagp, S, x + y, x); return; case 'S': RIGHT(diagm, W, x - y, x); return; } }; for (int i = 0; i < n; i++) { next_crash(i); } vector<bool> alive(n, true); while (!crashes.empty()) { set<int> boomships; for (auto [x, y]: crashes.begin()->second) { if (!alive[x] || !alive[y]) continue; boomships.insert(x); boomships.insert(y); } for (auto ship: boomships) { alive[ship] = false; auto [x, y, dir] = ships[ship]; int d = dir_num(dir); hor[d][y].erase(x); ver[d][x].erase(y); diagp[d][x + y].erase(x); diagm[d][x - y].erase(x); for (auto dir: {hor, ver, diagp, diagm}) { for (int card = 0; card < 4; card++) { int discr = dir == ver ? y : x; int repr; if (dir == hor) repr = y; if (dir == ver) repr = x; if (dir == diagp) repr = x + y; if (dir == diagm) repr = x - y; { auto it = dir[card][repr].upper_bound(discr); if (it != dir[card][repr].end()) { next_crash(it->second); } } { auto it = dir[card][repr].lower_bound(discr); if (it != dir[card][repr].begin() && !dir[card][repr].empty()) { next_crash(prev(it)->second); } } } } } crashes.erase(crashes.begin()); } for (int i = 0; i < n; i++) if (alive[i]) prnt(i + 1, '\n'); }

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

Main.cpp: In member function 'void Printer<BUFSIZE>::print_f(double)':
Main.cpp:171:29: warning: dereferencing type-punned pointer will break strict-aliasing rules [-Wstrict-aliasing]
  171 |        const uint64_t d = *((uint64_t*)&x);
      |                            ~^~~~~~~~~~~~~~
Main.cpp: In function 'int dir_num(char)':
Main.cpp:253:1: warning: control reaches end of non-void function [-Wreturn-type]
  253 | }
      | ^
Main.cpp: In member function 'void Printer<BUFSIZE>::flush() [with long unsigned int BUFSIZE = 65536]':
Main.cpp:225:13: warning: ignoring return value of 'ssize_t write(int, const void*, size_t)' declared with attribute 'warn_unused_result' [-Wunused-result]
  225 |        write(fd,buf,it-buf);
      |        ~~~~~^~~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...