제출 #749395

#제출 시각아이디문제언어결과실행 시간메모리
749395horiseunAliens (IOI16_aliens)C++17
4 / 100
3 ms340 KiB
#include <iostream> #include <vector> #include <tuple> #include <queue> #include <stack> #include <deque> #include <set> #include <map> #include <cmath> #include <random> #include <string> #include <cassert> #include <climits> #include <algorithm> #include <unordered_set> #include <unordered_map> using namespace std; #define ll long long #define f first #define s second void __print (int x) { cerr << x; } void __print (long x) { cerr << x; } void __print (long long x) { cerr << x; } void __print (unsigned x) { cerr << x; } void __print (unsigned long x) { cerr << x; } void __print (unsigned long long x) { cerr << x; } void __print (float x) { cerr << x; } void __print (double x) { cerr << x; } void __print (long double x) { cerr << x; } void __print (char x) { cerr << '\'' << x << '\''; } void __print (const char *x) { cerr << '\"' << x << '\"'; } void __print (const string &x) { cerr << '\"' << x << '\"'; } void __print (bool x) { cerr << (x ? "true" : "false"); } template<typename A> void __print (const A &x); template<typename A, typename B> void __print (const pair<A, B> &p); template<typename... A> void __print (const tuple<A...> &t); template<typename T> void __print (stack<T> s); template<typename T> void __print (queue<T> q); template<typename T, typename... U> void __print (priority_queue<T, U...> q); template<typename A> void __print (const A &x) { bool first = true; cerr << '{'; for (const auto &i : x) { cerr << (first ? "" : ","), __print(i); first = false; } cerr << '}'; } template<typename A, typename B> void __print (const pair<A, B> &p) { cerr << '('; __print(p.f); cerr << ','; __print(p.s); cerr << ')'; } template<typename... A> void __print (const tuple<A...> &t) { bool first = true; cerr << '('; apply([&first] (const auto &...args) { ((cerr << (first ? "" : ","), __print(args), first = false), ...); }, t); cerr << ')'; } template<typename T> void __print (stack<T> s) { vector<T> debugVector; while (!s.empty()) { T t = s.top(); debugVector.push_back(t); s.pop(); } reverse(debugVector.begin(), debugVector.end()); __print(debugVector); } template<typename T> void __print (queue<T> q) { vector<T> debugVector; while (!q.empty()) { T t = q.front(); debugVector.push_back(t); q.pop(); } __print(debugVector); } template<typename T, typename... U> void __print (priority_queue<T, U...> q) { vector<T> debugVector; while (!q.empty()) { T t = q.top(); debugVector.push_back(t); q.pop(); } __print(debugVector); } void _print() { cerr << "]\n"; } template <typename Head, typename... Tail> void _print (const Head &H, const Tail &...T) { __print(H); if (sizeof...(T)) cerr << ", "; _print(T...); } #ifdef DEBUG #define D(...) cerr << "Line:" << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__) #else #define D(...) #endif const double EPS = numeric_limits<double>::epsilon(); struct Line { ll m; ll c; ll k; double p; }; struct CHT { vector<Line> lines; double getX(ll m1, ll c1, ll m2, ll c2) { return (double) (c1 - c2) / (double) (m2 - m1 + EPS); } void addLine(ll m, ll c, ll k) { double p = LLONG_MIN; while (!lines.empty()) { p = getX(m, c, lines.back().m, lines.back().c); if (p < lines.back().p - EPS) lines.pop_back(); else break; } lines.push_back({m, c, k, p}); } pair<ll, int> getY(ll x) { int l = 0, r = lines.size() - 1, ret = 0; while (l <= r) { int m = (l + r) / 2; if (lines[m].p <= x + EPS) { ret = m; l = m + 1; } else { r = m - 1; } } assert(ret < lines.size()); return {lines[ret].m * x + lines[ret].c, lines[ret].k}; } void reset() { lines.clear(); } CHT() {} CHT(Line l) { addLine(l.m, l.c, l.k); } } ch; int sz; vector<ll> lf, rh; vector<pair<int, int>> temp; ll sm, lg, md, idx; pair<ll, int> calc(ll bonus) { vector<pair<ll, int>> dp(sz + 1); dp[0] = {0, 0}; ch.reset(); ch.addLine(-2 * lf[1], lf[1] * lf[1], 0); for (int i = 1; i <= sz; i++) { ll curr = rh[i] + 1; pair<ll, int> bst = ch.getY(curr); dp[i].f = bst.f + curr * curr + bonus; dp[i].s = bst.s + 1; if (i < sz) { ch.addLine(-2 * lf[i + 1], dp[i].f + lf[i + 1] * lf[i + 1] - max(0ll, rh[i] - lf[i + 1] + 1) * max(0ll, rh[i] - lf[i + 1] + 1), dp[i].s); } } return dp[sz]; } ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) { lf.push_back(-1); rh.push_back(-1); for (int i = 0; i < n; i++) { if (c[i] < r[i]) swap(r[i], c[i]); temp.push_back({c[i], r[i]}); } sort(temp.begin(), temp.end()); temp.erase(unique(temp.begin(), temp.end()), temp.end()); D(temp); for (pair<int, int> curr : temp) { if (curr.f == rh.back()) continue; while (lf.size() && curr.s <= lf.back() && rh.back() <= curr.f) { lf.pop_back(); rh.pop_back(); } lf.push_back(curr.s); rh.push_back(curr.f); } D(lf); D(rh); sm = 0, lg = (ll) (m + 1) * (ll) (m + 1), idx = 200, sz = lf.size() - 1; while (idx--) { md = (sm + lg) / 2; pair<ll, int> curr = calc(md); if (curr.s == k) { return curr.f - md * (ll) k; } if (curr.s < k) lg = md; else sm = md; } return calc(lg).f - lg * (ll) k; }

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

In file included from /usr/include/c++/10/cassert:44,
                 from aliens.cpp:12:
aliens.cpp: In member function 'std::pair<long long int, int> CHT::getY(long long int)':
aliens.cpp:152:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |   assert(ret < lines.size());
      |          ~~~~^~~~~~~~~~~~~~
#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...