이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusive
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
ll N,K;
cin>>N>>K;
pair<ll,ll> arr[N];
bool Yiszero = 1;
for(ll i = 0;i < N;i++){
cin>>arr[i].first>>arr[i].second; //X[i], Y[i]
if(arr[i].second != 0) Yiszero = 0;
}
sort(arr,arr + N);
if(N <= 1000){
vector<ll> v;
for(ll i = 0;i < N;i++){
for(ll j = 0;j < i;j++){
v.push_back({abs(arr[i].first - arr[j].first) + abs(arr[i].second - arr[j].second)});
}
}
sort(v.begin(),v.end());
for(ll i = 0;i < K;i++){
cout<<v[i]<<'\n';
}
}else{
priority_queue<ll> pq;
map<pair<ll,ll>,bool> done;
ll cnt = 0;
while(cnt < 10000000){
ll a = rand(0,N - 2);
ll b = rand(a + 1,N - 1);
if(done[{a,b}]) continue;
done[{a,b}] = 1;
ll sum = abs(arr[a].first - arr[b].first) + abs(arr[a].second - arr[b].second);
if(pq.size() < K){
pq.push(sum);
}else if(sum < pq.top()){
pq.pop();
pq.push(sum);
}
}
deque<ll> ans;
while(!pq.empty()){
ans.push_front(pq.top());
pq.pop();
}
for(ll i = 0;i < K;i++){
cout<<ans[i]<<'\n';
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
road_construction.cpp: In function 'int main()':
road_construction.cpp:39:17: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
39 | if(pq.size() < K){
| ~~~~~~~~~~^~~
road_construction.cpp:12:7: warning: variable 'Yiszero' set but not used [-Wunused-but-set-variable]
12 | bool Yiszero = 1;
| ^~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |