제출 #858595

#제출 시각아이디문제언어결과실행 시간메모리
858595resting추월 (IOI23_overtaking)C++17
19 / 100
16 ms1300 KiB
#include <bits/stdc++.h> using namespace std; #define int long long vector<pair<int, int>> restriction; // if "starts after a", has to "end after b" yk int x, l; bool comp(const pair<int,int>&a, const pair<int,int>&b){ if(a.second == b.second) return a.first > b.first; return a.second < b.second; } vector<pair<int,int>> fix(vector<pair<int,int>> shit){ vector<pair<int,int>> res; sort(shit.begin(), shit.end()); for(int i = shit.size()-1; i >= 0; i--){ if(res.size() && shit[i].first >= res.back().first) continue; res.push_back(shit[i]); } reverse(res.begin(), res.end()); return res; } void init(int32_t L, int32_t N, std::vector<long long> T, std::vector<int32_t> W, int32_t X, int32_t M, std::vector<int32_t> S) { x = X; l = L; vector<vector<pair<int, int>>> restrictions(M);// yes vector<pair<int, int>> cur; for (int i = 0; i < N; i++) if (W[i] > X) cur.push_back({ T[i], W[i] - X }); for (int i = 0; i < M-1; i++) { sort(cur.begin(), cur.end()); vector<pair<int, int>> res; const int T = cur.size(); for (int j = 0; j < T; j++) res.push_back({ cur[j].first + cur[j].second * (S[i + 1] - S[i]), cur[j].second }); for (int j = 0; j < T - 1; j++) if (res[j].first > res[j + 1].first) res[j + 1].first = res[j].first; int p = -1; for (int j = 0; j < T; j++) { if(res[j].first != p){ if(j + 1 == T || cur[j].first != cur[j+1].first){ p = res[j].first; restrictions[i].push_back({ cur[j].first+1, res[j].first }); //start, end } } } for(int j = 1; j < restrictions[i].size(); j++){ assert(restrictions[i][j].first > restrictions[i][j-1].first); assert(restrictions[i][j].second > restrictions[i][j-1].second); } //for(int j = 0; j < restrictions[i].size(); j++) cout<<restrictions[i][j].first<<","<<restrictions[i][j].second<<endl; //cout<<endl; swap(res, cur); } //restrictions i guess ["start after i has to end after j"] restriction = restrictions[0]; // cout<<"restriction"<<endl; // for(auto &x : restriction) cout<<x.first<<" "<<x.second<<endl; for (int i = 1; i < M; i++) { //transition from prev ??? //two pointers vector<pair<int, int>> nice; auto l1 = restriction, l2 = restrictions[i]; l1 = fix(l1); l2 = fix(l2); int p1 = l1.size() - 1; int p2 = l2.size() - 1; int cur = numeric_limits<long long>::max(); while (p1 >= 0 || p2 >= 0) { // cout<<"A: "<<p1<<","<<p2<<endl; if (p1 < 0) { nice.push_back(l2[p2]); cur = l2[p2].first; p2--; } else if (p2 < 0) { nice.push_back(l1[p1]); cur = l1[p1].first; p1--; } else if (l1[p1].second < l2[p2].second) { int a = l2[p2].first; while (l1[p1].second >= l2[p2].first) { a = min(a, l1[p1].first); p1--; } l2[p2].first = a; nice.push_back(l2[p2]); cur = l2[p2].first; p2--; } else { assert(l1[p1].second >= l2[p2].second); nice.push_back(l1[p1]); cur = l1[p1].first; p1--; } while (p1 >= 0 && l1[p1].first >= cur) p1--; while (p2 >= 0 && l2[p2].first >= cur) p2--; } swap(restriction, nice); restriction = fix(restriction); //reverse(restriction.begin(), restriction.end()); // cout<<"restriction"<<endl; // for(auto &x : restriction) cout<<x.first<<" "<<x.second<<endl; } return; } long long arrival_time(long long Y) { auto yes = prev(upper_bound(restriction.begin(), restriction.end(), make_pair( Y, numeric_limits<long long>::max() )))- restriction.begin(); if (yes >= 0 && yes <= restriction.size()) Y = max(Y, restriction[yes].second); return Y + x * l; }

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

overtaking.cpp: In function 'void init(int32_t, int32_t, std::vector<long long int>, std::vector<int>, int32_t, int32_t, std::vector<int>)':
overtaking.cpp:44:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int j = 1; j < restrictions[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~
overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:110:25: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     if (yes >= 0 && yes <= restriction.size()) Y = max(Y, restriction[yes].second);
      |                     ~~~~^~~~~~~~~~~~~~~~~~~~~
#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...