# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
893380 | vjudge1 | Road Construction (JOI21_road_construction) | C++17 | 616 ms | 22356 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define rnd(l, r) uniform_int_distribution<int>(l, r)(rng)
using namespace std;
void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
int pow(int a,int b,int m){int ans=1;while(b){if(b&1){ans=(ans*a)%m;}b>>=1;a=(a*a)%m;}return ans;}
int binpow(int a,int b){int ans=1;while(b){if(b&1){ans=(ans*a);}b>>=1;a=(a*a);}return ans;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 3e5 + 10, inf = 1e9;
int x[N], y[N];
int k;
main(){
iostream::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n >> k;
set <int> sty;
for(int i = 1; i <= n; i++){
cin >> x[i] >> y[i];
}
if(n <= 1000){
vector <int> dists;
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
dists.pb(abs(x[i] - x[j]) + abs(y[i] - y[j]));
}
}
sort(all(dists));
for(int i = 0; i < k; i++){
cout << dists[i] <<"\n";
}
}else{
multiset <pair <int,int> > st;
sort(x + 1, x + n + 1);
for(int i = 1; i <= n - 1; i++){
st.insert({x[i + 1] - x[i], i + 1});
}
while(k--){
cout << st.begin() -> ff << endl;
pair <int,int> f = *st.begin();
st.erase(st.begin());
if(f.ss == n)continue;
st.insert({f.ff + x[f.ss + 1] - x[f.ss], f.ss + 1});
}
}
//cout << endl;
}
/*
* Before implementing the problem:
Do I understand the problem correctly?
Which places are tricky? What do I need to remember to implement them correctly?
Which place is the heaviest by implementation? Can I do it simpler?
Which place is the slowest? Where do I need to be careful about constant factors and where I can choose slower but simpler implementation?
----------------------------------
If not AC:
Did you remember to do everything to handle the tricky places you thought about before?
Is the solution correct?
Do I understand the problem correctly?
----------------------------------
If you have a test on which the solution gives wrong answer:
Is the solution doing what it was supposed to do?
Is the problem in the code or in the idea?
*/
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |