QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#413122 | #1768. 廊桥分配 | x-camp | Compile Error | / | / | C++17 | 3.1kb | 2024-05-17 06:16:40 | 2024-05-17 06:16:40 |
Judging History
answer
=#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <fstream>
#include <cstring>
using namespace std;
#define ar first
#define de second
int N, m1, m2;
#define MX 100005
vector<pair<int,int>> s1, s2;
int parked[MX];
vector<pair<pair<int,int>,pair<int,int>>> t1, t2;
int ans;
int schedule (vector<pair<int,int>> &s, int sz, vector<pair<pair<int,int>,pair<int,int>>> & t) {
if (t.empty()) {
for (int i=0; i<s.size(); i++) {
auto p = s[i];
t.push_back({p,{1,i}});
t.push_back({{p.second,p.first},{2,i}});
}
sort(t.begin(),t.end());
}
vector<int> parkedAir;
vector<bool> in( (int) s.size());
int cur = 0;
int endtime = 0;
int parked = 0;
for (int i=0; i<t.size();i++) {
auto &e = t[i];
if (e.second.first == 1) { // arrival time
if (cur < sz ) {
cur++;
parked++;
parkedAir.push_back(cur);
in[e.second.second] = true; //parked in bridge
}
}
else { // departure time
if (in[e.second.second]) cur --;
}
}
return parked;
}
int res[MX];
void quadSearch(int start, int end) {
if (start ==0)
res[start] = schedule(s1, start, t1) + schedule(s2,N-start , t2);
if (end ==N)
res[end] = schedule(s1, end, t1) + schedule(s2,N-end , t2);
if (end - start <10) {
for (int i = max(0,start - 100); i<=min(N, end+100); i++) {
res[i] = schedule(s1, i, t1) + schedule(s2, N-i, t2);
ans = max(ans, res[i]);
}
} else {
int left = start + (end -start)/4, right = start + (end-start)*3/4;
int mid = (start + end) /2;
int q1 = schedule(s1, left, t1) + schedule(s2,N-left , t2);
int q2 = schedule(s1, mid, t1) + schedule(s2,N-mid , t2);
int q3 = schedule(s1, right, t1) + schedule(s2,N-right , t2);
if (start > q2) {
if (q2 >= q3) quadSearch(start, mid);
else quadSearch(start, right);
}
else if (end > q2) {
if (q2 >= q1) quadSearch(mid, end);
else quadSearch(left, end);
}
else if (q2 > q1 && q2 > q3) quadSearch(left, right);
else if (q1 > q2 && q2 >= q3) quadSearch(start, right);
else if (q3 >= q2 && q2 >=q1) quadSearch(left, end);
else {
quadSearch(start+2, end-2);
}
}
return;
}
int main() {
cin >> N >> m1 >> m2;
for (int i=0; i<m1; i++) {
int a,b;
cin >> a >> b;
s1.push_back({a,b});
}
for (int i=0; i<m2; i++) {
int a,b;
cin >> a >> b;
s2.push_back({a,b});
}
int best = 0;
/*for (int i=0; i<=N; i++) {
best = max(best, schedule(s1, i,t1) + schedule(s2, N-i,t2));
}*/
quadSearch(0, N);
/*
cout << best << " " << ans << endl;
for (int i=0; i<=N; i++)
cout << res[i] << " ";
cout << endl; */
cout << ans;
return 0;
}
詳細信息
answer.code:1:2: error: stray ‘#’ in program 1 | =#include <iostream> | ^ answer.code:1:1: error: expected unqualified-id before ‘=’ token 1 | =#include <iostream> | ^ In file included from /usr/include/c++/13/bits/stl_algobase.h:62, from /usr/include/c++/13/vector:62, from answer.code:2: /usr/include/c++/13/ext/type_traits.h:164:35: error: ‘constexpr const bool __gnu_cxx::__is_null_pointer’ redeclared as different kind of entity 164 | __is_null_pointer(std::nullptr_t) | ^ /usr/include/c++/13/ext/type_traits.h:159:5: note: previous declaration ‘template<class _Type> constexpr bool __gnu_cxx::__is_null_pointer(_Type)’ 159 | __is_null_pointer(_Type) | ^~~~~~~~~~~~~~~~~ /usr/include/c++/13/ext/type_traits.h:164:26: error: ‘nullptr_t’ is not a member of ‘std’ 164 | __is_null_pointer(std::nullptr_t) | ^~~~~~~~~ In file included from /usr/include/c++/13/bits/stl_pair.h:60, from /usr/include/c++/13/bits/stl_algobase.h:64: /usr/include/c++/13/type_traits:275:27: error: ‘size_t’ has not been declared 275 | template <typename _Tp, size_t = sizeof(_Tp)> | ^~~~~~ /usr/include/c++/13/type_traits:510:26: error: ‘std::size_t’ has not been declared 510 | template<typename _Tp, std::size_t _Size> | ^~~ /usr/include/c++/13/type_traits:511:25: error: ‘_Size’ was not declared in this scope 511 | struct is_array<_Tp[_Size]> | ^~~~~ /usr/include/c++/13/type_traits:511:31: error: template argument 1 is invalid 511 | struct is_array<_Tp[_Size]> | ^ /usr/include/c++/13/type_traits:617:33: error: ‘nullptr_t’ is not a member of ‘std’ 617 | struct is_null_pointer<std::nullptr_t> | ^~~~~~~~~ /usr/include/c++/13/type_traits:617:42: error: template argument 1 is invalid 617 | struct is_null_pointer<std::nullptr_t> | ^ /usr/include/c++/13/type_traits:621:48: error: template argument 1 is invalid 621 | struct is_null_pointer<const std::nullptr_t> | ^ /usr/include/c++/13/type_traits:625:51: error: template argument 1 is invalid 625 | struct is_null_pointer<volatile std::nullptr_t> | ^ /usr/include/c++/13/type_traits:629:57: error: template argument 1 is invalid 629 | struct is_null_pointer<const volatile std::nullptr_t> | ^ /usr/include/c++/13/type_traits:914:26: error: ‘size_t’ has not been declared 914 | template<typename _Tp, size_t _Size> | ^~~~~~ /usr/include/c++/13/type_traits:915:40: error: ‘_Size’ was not declared in this scope 915 | struct __is_array_known_bounds<_Tp[_Size]> | ^~~~~ /usr/include/c++/13/type_traits:915:46: error: template argument 1 is invalid 915 | struct __is_array_known_bounds<_Tp[_Size]> | ^ /usr/include/c++/13/type_traits:1348:37: error: ‘size_t’ is not a member of ‘std’ 1348 | : public integral_constant<std::size_t, alignof(_Tp)> | ^~~~~~ /usr/include/c++/13/type_traits:1348:57: error: template argument 1 is invalid 1348 | : public integral_constant<std::size_t, alignof(_Tp)> | ^ /usr/include/c++/13/type_traits:1348:57: note: invalid template non-type parameter /usr/include/c++/13/type_traits:1357:37: error: ‘size_t’ is not a member of ‘std’ 1357 | : public integral_constant<std::size_t, 0> { }; | ^~~~~~ /usr/include/c++/13/type_traits:1357:46: error: template argument 1 is invalid 1357 | : public integral_constant<std::size_t, 0> { }; | ^ /usr/include/c++/13/type_traits:1357:46: note: invalid template non-type parameter /usr/include/c++/13/type_traits:1359:26: error: ‘std::size_t’ has not been declared 1359 | template<typename _Tp, std::size_t _Size> | ^~~ /usr/include/c++/13/type_traits:1360:21: error: ‘_Size’ was not declared in this scope 1360 | struct rank<_Tp[_Size]> | ^~~~~ /usr/include/c++/13/type_traits:1360:27: error: template argument 1 is invalid 1360 | struct rank<_Tp[_Size]> | ^ /usr/include/c++/13/type_traits:1361:37: error: ‘size_t’ is not a member of ‘std’ 1361 | : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { }; | ^~~~~~ /usr/include/c++/13/type_traits:1361:65: error: template argument 1...