제출 #151525

#제출 시각아이디문제언어결과실행 시간메모리
151525edenooo최적의 팀 구성 (FXCUP4_squad)C++17
19 / 100
351 ms42756 KiB
#include "squad.h" #include<vector> #include<algorithm> using namespace std; #define INF 9'000'000'000'000'000'000LL #define ll long long struct Fraction { ll a, b; // a/b bool operator< (Fraction &n) { if (a == -INF) return true; //틀린 이유 if (n.a == -INF) return false; ll ta, tb, tc, td; ta = a; tb = b; tc = n.a; td = n.b; if (tb < 0) { ta *= -1; tb *= -1; } if (td < 0) { tc *= -1; td *= -1; } return ta * td < tb * tc; } bool operator<= (Fraction &n) { if (a == -INF) return true; if (n.a == -INF) return false; ll ta, tb, tc, td; ta = a; tb = b; tc = n.a; td = n.b; if (tb < 0) { ta *= -1; tb *= -1; } if (td < 0) { tc *= -1; td *= -1; } return ta * td <= tb * tc; } }; struct Line { ll a, b; Fraction s; int idx; bool operator< (const Line &n) const { if (a != n.a) return a < n.a; return b > n.b; } }; int N; vector<Line> v, re; Fraction Cross(Line &A, Line &B) { return { (B.b - A.b),(A.a - B.a) }; } struct CHT { vector<Line> cht; void insert(Line n) { while (!cht.empty()) { if (cht.back().a == n.a) { if (cht.back().b <= n.b) { re.push_back(cht.back()); cht.pop_back(); } else return; } else { Fraction c = Cross(cht.back(), n); n.s.a = c.a; n.s.b = c.b; if (n.s <= cht.back().s) //틀린 이유 { re.push_back(cht.back()); cht.pop_back(); } else break; } } cht.push_back(n); } int query(Fraction x) { if (cht.empty()) return -1; int lo = 0, hi = (int)cht.size(); for (int i = 0; i < 20; i++) { int mid = lo + hi >> 1; if (x < cht[mid].s) hi = mid; else lo = mid; } return lo; } } x, xx, y, yy; void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){ v.reserve(300301); re.reserve(300301); x.cht.reserve(300301); xx.cht.reserve(300301); y.cht.reserve(300301); yy.cht.reserve(300301); N = A.size(); for (int i = 0; i < N; i++) { Line n = { (ll)A[i], (ll)P[i], {-INF, 1LL}, i }; //-INF : 틀린 이유 v.push_back(n); } sort(v.begin(), v.end()); for (int i = 0; i < v.size(); i++) x.insert(v[i]); sort(re.begin(), re.end()); int M = (int)re.size(); for (int i = 0; i < M; i++) //틀린 이유 re[i].s = { -INF, 1LL }; for (int i = 0; i < M; i++) xx.insert(re[i]); v.clear(); re.clear(); for (int i = 0; i < N; i++) { Line n = { (ll)D[i], (ll)P[i], {-INF, 1LL}, i }; v.push_back(n); } sort(v.begin(), v.end()); for (int i = 0; i < v.size(); i++) y.insert(v[i]); sort(re.begin(), re.end()); M = (int)re.size(); for (int i = 0; i < M; i++) re[i].s = { -INF, 1LL }; for (int i = 0; i < M; i++) yy.insert(re[i]); v.clear(); re.clear(); } long long BestSquad(int X, int Y){ Fraction pos = { (ll)X, (ll)Y }; vector<pair<ll, int> > L, R; int i = x.query(pos); L.push_back({ x.cht[i].a*X + x.cht[i].b*Y, x.cht[i].idx }); int ii = xx.query(pos); if (ii != -1) L.push_back({ xx.cht[ii].a*X + xx.cht[ii].b*Y, xx.cht[ii].idx }); if (i - 1 >= 0) L.push_back({ x.cht[i - 1].a*X + x.cht[i - 1].b*Y, x.cht[i - 1].idx }); if (i + 1 < (int)x.cht.size()) L.push_back({ x.cht[i + 1].a*X + x.cht[i + 1].b*Y, x.cht[i + 1].idx }); int j = y.query(pos); R.push_back({ y.cht[j].a*X + y.cht[j].b*Y, y.cht[j].idx }); int jj = yy.query(pos); if (jj != -1) R.push_back({ yy.cht[jj].a*X + yy.cht[jj].b*Y, yy.cht[jj].idx }); if (j - 1 >= 0) R.push_back({ y.cht[j - 1].a*X + y.cht[j - 1].b*Y, y.cht[j - 1].idx }); if (j + 1 < (int)y.cht.size()) R.push_back({ y.cht[j + 1].a*X + y.cht[j + 1].b*Y, y.cht[j + 1].idx }); ll res = 0; for (int i = 0; i < L.size(); i++) for (int j = 0; j < R.size(); j++) if (L[i].second != R[j].second) res = max(res, L[i].first + R[j].first); return res; }

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

squad.cpp: In member function 'int CHT::query(Fraction)':
squad.cpp:89:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo + hi >> 1;
              ~~~^~~~
squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++)
                  ~~^~~~~~~~~~
squad.cpp:124:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++)
                  ~~^~~~~~~~~~
squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:160:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < L.size(); i++)
                  ~~^~~~~~~~~~
squad.cpp:161:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < R.size(); j++)
                   ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...