제출 #1010003

#제출 시각아이디문제언어결과실행 시간메모리
1010003boris_mihov추월 (IOI23_overtaking)C++17
39 / 100
3571 ms31236 KiB
#include "overtaking.h" #include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> typedef long long llong; const int MAXN = 1000 + 10; const int MAXQ = 5000 + 10; llong x; int n, m, l; std::vector <int> s; std::vector <std::pair <llong,int>> buses; std::vector <std::pair <llong,llong>> t[MAXN]; std::vector <llong> ifBegining[MAXN]; llong min[MAXN]; int findIntersection(int pos, llong time) { int l = 0, r = t[pos].size(), mid; while (l < r - 1) { mid = l + r >> 1; if (t[pos][mid].first < time) l = mid; else r = mid; } return l; } long long my_arrival_time(int pos, llong time) { for (int i = pos ; i + 1 < m ; ++i) { int l = 0, r = t[i].size(), mid; while (l < r - 1) { mid = l + r >> 1; if (t[i][mid].first < time) l = mid; else r = mid; } time = std::max(time + 1LL * x * (s[i + 1] - s[i]), t[i][l].second); } return time; } void init(int L, int N, std::vector <long long> T, std::vector <int> W, int X, int M, std::vector <int> S) { n = N; m = M; s = S; x = X; for (int i = 0 ; i < n ; ++i) { buses.push_back({T[i], W[i]}); } for (int i = 0 ; i + 1 < m ; ++i) { t[i].push_back({-1, 0}); std::vector <std::pair <llong,int>> newBuses; std::sort(buses.begin(), buses.end()); for (const auto &[time, w] : buses) { llong arrive = 1LL * (s[i + 1] - s[i]) * w + time; if (arrive > t[i].back().second) { t[i].push_back({time, arrive}); } newBuses.push_back({t[i].back().second, w}); } buses = newBuses; } std::vector <std::pair <int,int>> v; for (int i = 0 ; i + 1 < m ; ++i) { for (int j = 1 ; j < t[i].size() ; ++j) { v.push_back({i, j}); } } std::sort(v.begin(), v.end(), [&](auto &a, auto &b) { return t[a.first][a.second].second - 1LL * s[a.first + 1] * x > t[b.first][b.second].second - 1LL * s[b.first + 1] * x; }); for (int i = 0 ; i + 1 < m ; ++i) { ifBegining[i].resize(t[i].size()); } std::fill(min, min + m, 1e18); for (const auto &[i, j] : v) { bool done = false; ifBegining[i][j] = 1LL * (s[m - 1] - s[i + 1]) * x + t[i][j].second; for (int u = i + 1 ; u + 1 < m ; ++u) { // if (min[u] >= t[i][j].second - 1LL * s[i + 1] * x) // { // continue; // } for (int v = 1 ; v < t[u].size() ; ++v) { if (t[i][j].second - 1LL * s[i + 1] * x > t[u][v].first - 1LL * s[u] * x && t[i][j].second - 1LL * s[i + 1] * x < t[u][v].second - 1LL * s[u + 1] * x) { ifBegining[i][j] = std::max(ifBegining[i][j], ifBegining[u][v]); done = true; } } // assert(r != t[u].size()); // ifBegining[i][j] = ifBegining[u][mid]; if (done) break; } min[i] = std::min(min[i], t[i][j].first - 1LL * s[i] * x); } } long long arrival_time(llong time) { for (int i = 0 ; i + 1 < m ; ++i) { int l = 0, r = t[i].size(), mid; while (l < r - 1) { mid = l + r >> 1; if (t[i][mid].first < time) l = mid; else r = mid; } if (l != 0 && time + 1LL * x * (s[i + 1] - s[i]) < t[i][l].second) { return ifBegining[i][l]; } time += 1LL * x * (s[i + 1] - s[i]); } return time; }

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

overtaking.cpp: In function 'int findIntersection(int, llong)':
overtaking.cpp:25:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         mid = l + r >> 1;
      |               ~~^~~
overtaking.cpp: In function 'long long int my_arrival_time(int, llong)':
overtaking.cpp:40:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |             mid = l + r >> 1;
      |                   ~~^~~
overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:85:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for (int j = 1 ; j < t[i].size() ; ++j)
      |                          ~~^~~~~~~~~~~~~
overtaking.cpp:113:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             for (int v = 1 ; v < t[u].size() ; ++v)
      |                              ~~^~~~~~~~~~~~~
overtaking.cpp: In function 'long long int arrival_time(llong)':
overtaking.cpp:140:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  140 |             mid = l + r >> 1;
      |                   ~~^~~
#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...