Submission #944946

#	Time	Username	Problem	Language	Result	Execution time	Memory
944946		dsyz	Road Construction (JOI21_road_construction)	C++17	5 / 100	10091 ms	280760 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
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
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2> &pair) const {
        auto hash1 = std::hash<T1>{}(pair.first);
        auto hash2 = std::hash<T2>{}(pair.second);
        return hash1 ^ hash2;
    }
};
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,K;
	cin>>N>>K;
	pair<ll,ll> arr[N];
	for(ll i = 0;i < N;i++){
		cin>>arr[i].first>>arr[i].second; //X[i], Y[i]
	}
	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;
		unordered_map<pair<ll,ll>, bool, pair_hash> done;
		ll cnt = 0;
		while(cnt < 5000000){
			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';
		}
	}
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:47: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]
   47 |    if(pq.size() < K){
      |       ~~~~~~~~~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35