結果

問題 No.2248 max(C)-min(C)
ユーザー siman
提出日時 2023-03-19 23:13:41
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 357 ms / 3,000 ms
コード長 1,598 bytes
コンパイル時間 5,639 ms
コンパイル使用メモリ 143,220 KB
実行使用メモリ 23,116 KB
最終ジャッジ日時 2024-09-18 13:54:21
合計ジャッジ時間 13,293 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <cassert>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <climits>
#include <map>
#include <queue>
#include <set>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
struct Node {
int i;
int c;
Node(int i = -1, int c = -1) {
this->i = i;
this->c = c;
}
bool operator>(const Node &n) const {
return c > n.c;
}
};
int main() {
int N;
cin >> N;
vector<int> A(N);
vector<int> B(N);
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
for (int i = 0; i < N; ++i) {
cin >> B[i];
}
vector<int> nums;
priority_queue <Node, vector<Node>, greater<Node>> pque;
int cand[N][5];
for (int i = 0; i < N; ++i) {
int a = A[i];
int b = B[i];
if (a > b) {
int t = a;
a = b;
b = t;
}
cand[i][0] = INT_MIN;
cand[i][1] = a;
cand[i][2] = (a + b) / 2;
cand[i][3] = b;
cand[i][4] = INT_MAX;
nums.push_back(a);
nums.push_back(b);
nums.push_back((a + b) / 2);
pque.push(Node(i, INT_MIN));
pque.push(Node(i, a));
pque.push(Node(i, b));
pque.push(Node(i, (a + b) / 2));
pque.push(Node(i, INT_MAX));
}
sort(nums.begin(), nums.end());
vector<int> cur_pos(N, 0);
int ans = INT_MAX;
int max_c = 0;
for (int min_c : nums) {
while (not pque.empty() && pque.top().c < min_c) {
Node node = pque.top();
pque.pop();
cur_pos[node.i]++;
max_c = max(max_c, cand[node.i][cur_pos[node.i]]);
}
ans = min(ans, max_c - min_c);
}
cout << ans << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0