Submission #844856

#TimeUsernameProblemLanguageResultExecution timeMemory
844856ogkostyaOvertaking (IOI23_overtaking)C++17
0 / 100
1 ms604 KiB
#include "overtaking.h" #include <algorithm> #include <utility> #include <list> #include <climits> std::vector<std::vector<std::pair<long long, long long>>> SS(1001, std::vector<std::pair<long long, long long>>()); struct sort1 { inline bool operator() (const std::pair<long long, int>& a, const std::pair<long long, int>& b) { if (a.first == b.first) return a.second < b.second; return a.first < b.first; } }; class leaf { public: leaf(long long _a, long long _b, long long _r) { a = _a; b = _b; r = _r; } long long a, b, r; }; struct sort2 { inline bool operator() (leaf const& a, leaf const& b) { return b.r < a.r; } }; int _M; std::vector<int> _S; int _X; std::vector<leaf> ans; std::vector<leaf> J(std::vector<leaf> & X) { std::vector<leaf> Y; if (X.size() > 0) { std::sort(X.begin(), X.end(), sort2()); long long a, b, r = -1, ma = LLONG_MAX; for (size_t i = 0; i < X.size(); i++) { if (X[i].r != r) { if (r == -1) { r = X[i].r; a = X[i].a; b = X[i].b; } else { if (ma > a) { if (b >= ma) b = ma - 1; Y.push_back(leaf(a, b, r)); ma = a; } r = X[i].r; a = X[i].a; b = X[i].b; } } else { if (a > X[i].a) a = X[i].a; if (b < X[i].b) b = X[i].b; } } if (ma > a) { if (b >= ma) b = ma - 1; Y.push_back(leaf(a, b, r)); } std::reverse(Y.begin(), Y.end()); } return Y; } void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) { _X = X; _M = M; _S = S; std::vector<std::pair<long long, int>> TW; TW.reserve(N); for (int i = 0; i < N; i++) { if (W[i] < X) continue; TW.push_back(std::make_pair(T[i], W[i])); } long long mb = 0; std::vector<leaf> next; std::vector<leaf> curr; long long mr = 0; int curr_i; for (int j = 1; j < M; j++) { std::sort(TW.begin(), TW.end(), sort1()); mb = 0; mr = 0; curr_i = 0; for (int i = 0; i < TW.size(); i++) { long long a = TW[i].first; long long b = a + 1LL * (_S[j] - _S[j - 1]) * TW[i].second; if (b < mb) b = mb; else mb = b; if (SS[j].size() == 0 || SS[j].back().second != b && (i + 1 == TW.size() || TW[i].first != TW[i + 1].first)) { SS[j].push_back(std::make_pair(a, b)); long long fa = a - 1LL * X * _S[j - 1] + 1; long long fb = b - 1LL * X * _S[j]; long long fc = b + 1LL * (_S[M - 1] - _S[j]) * X; if (fc < mr) { leaf front = leaf(fa, fb, b); next.push_back(front); } else { leaf front = leaf(fa, fb, fc); ans.push_back(front); } } while (curr_i < curr.size()) { if (curr[curr_i].r < a) { long long fc = curr[curr_i].r + 1LL * (_S[M - 1] - _S[j - 1]) * X; if (fc >= mr) { curr[curr_i].r = fc; ans.push_back(curr[curr_i]); curr_i++; continue; } curr[curr_i].r = curr[curr_i].r + 1LL * (_S[j] - _S[j - 1]) * X; next.push_back(curr[curr_i]); curr_i++; continue; } else { if (i + 1 == TW.size() || TW[i + 1].first > curr[curr_i].r) { long long fc = curr[curr_i].r + 1LL * (_S[j] - _S[j - 1]) * X; if (fc < b) fc = b; curr[curr_i].r = fc; next.push_back(curr[curr_i]); curr_i++; continue; } else { break; } } } long long c = b + 1LL * (_S[M - 1] - _S[j]) * TW[i].second; if (mr < c) mr = c; TW[i].first = b; } curr = J(next); } ans = J(ans); } long long arrival_time(long long Y) { long long a = Y; long long b = a + 1LL * _S[_M - 1] * _X; if (ans[0].a <= a) { int l = 0, r = ans.size()-1; while (l < r) { int m = (l + r + 1) / 2; if (m == ans.size()) { break; } else if (ans[m].a <= a) { l = m; } else { r = m - 1; } } if (ans[l].b >= a) b = ans[l].r; } return b; }

Compilation message (stderr)

overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:127:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         for (int i = 0; i < TW.size(); i++)
      |                         ~~^~~~~~~~~~~
overtaking.cpp:137:73: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |             if (SS[j].size() == 0 || SS[j].back().second != b && (i + 1 == TW.size() || TW[i].first != TW[i + 1].first))
      |                                                                   ~~~~~~^~~~~~~~~~~~
overtaking.cpp:137:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  137 |             if (SS[j].size() == 0 || SS[j].back().second != b && (i + 1 == TW.size() || TW[i].first != TW[i + 1].first))
      |                                      ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
overtaking.cpp:156:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<leaf>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |             while (curr_i < curr.size())
      |                    ~~~~~~~^~~~~~~~~~~~~
overtaking.cpp:175:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |                     if (i + 1 == TW.size() || TW[i + 1].first > curr[curr_i].r)
      |                         ~~~~~~^~~~~~~~~~~~
overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:216:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<leaf>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |             if (m == ans.size())
      |                 ~~^~~~~~~~~~~~~
overtaking.cpp: In function 'std::vector<leaf> J(std::vector<leaf>&)':
overtaking.cpp:91:13: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |             if (b >= ma)
      |             ^~
overtaking.cpp:24:11: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   24 |         a = _a;
      |         ~~^~~~
overtaking.cpp:54:19: note: 'a' was declared here
   54 |         long long a, b, r = -1, ma = LLONG_MAX;
      |                   ^
#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...