oj.uz

Submission #944948

# Submission time Handle Problem Language Result Execution time Memory
944948 2024-03-13T08:43:05 Z dsyz Road Construction (JOI21_road_construction) C++17
5 / 100
 10000 ms 432792 KB 
#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];
	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;
		map<pair<ll,ll>,bool> done;
		ll cnt = 0;
		while(cnt < 1000000){
			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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 6956 KB Output is correct
2 Correct 51 ms 7084 KB Output is correct
3 Correct 32 ms 5056 KB Output is correct
4 Correct 32 ms 5064 KB Output is correct
5 Correct 49 ms 5820 KB Output is correct
6 Correct 16 ms 6352 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10120 ms 419428 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10069 ms 432792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10069 ms 432792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 6956 KB Output is correct
2 Correct 51 ms 7084 KB Output is correct
3 Correct 32 ms 5056 KB Output is correct
4 Correct 32 ms 5064 KB Output is correct
5 Correct 49 ms 5820 KB Output is correct
6 Correct 16 ms 6352 KB Output is correct
7 Execution timed out 10039 ms 415680 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 6956 KB Output is correct
2 Correct 51 ms 7084 KB Output is correct
3 Correct 32 ms 5056 KB Output is correct
4 Correct 32 ms 5064 KB Output is correct
5 Correct 49 ms 5820 KB Output is correct
6 Correct 16 ms 6352 KB Output is correct
7 Execution timed out 10120 ms 419428 KB Time limit exceeded
8 Halted 0 ms 0 KB -