oj.uz

Submission #893498

# Submission time Handle Problem Language Result Execution time Memory
893498 2023-12-27T05:54:30 Z vjudge1 Road Construction (JOI21_road_construction) C++17
18 / 100
 382 ms 21624 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

bool YES(bool f){ if(f) cout << "Yes\n" ; else cout << "No\n" ; return f ; }
void YES(){YES(1);}
void NO(){YES(0);}
void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
//#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ios ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
#define int long long
#define ld long double
#define pii pair <int , int>
#define all(x) x.begin() , x.end()
#define ff first
#define ss second
#define endl '\n'

const int N = 2e6 + 5 ;
const int inf = 1e18 ;
const int mod = 998244353 ;
const double eps = 1e-8 ;

int binpow( int a , int b ){
  if ( b == 0 ) return 1 ;
  int x = binpow ( a , b/2 ) ;
  if ( !(b%2) ) return (x*x) ;
  return (x*x*a) ;
}
template <class T>
bool chmax( T& x , const T& y ){
  bool f = 0 ;
  if ( x < y ) x = y , f = 1 ;
  return f ;
}
template <class T>
bool chmin( T &x , const T &y ){
  bool f = 0 ;
  if ( x > y ) x = y , f = 1 ;
  return f ;
}

//code

int n , k ;
vector <int> ans ;
pii a[N] ;
set <pair <int , pii>> st ;

int dist ( int x , int y , int x1 , int y1 ){
	return abs(x-x1)+abs(y-y1) ;
}

int slow ( int l , int r ){
	int res = inf ;
	for ( int i = l ; i <= r ; i ++ ){
		for ( int j = i+1 ; j <= r ; j ++ ) chmin ( res , dist( a[i].ff , a[i].ss , a[j].ff , a[j].ss ) ) ;
	}
	return res ;
}

int get ( int l , int r ){
	
	if ( r - l + 1 < 5 ) return slow(l,r) ;
	int mid = ( l + r ) / 2 ;
	int ml = get ( l , mid ) ;
	int mr = get ( mid+1 , r ) ;
	int mn = min ( ml , mr ) ;
	int ans = mn ;
	vector <pii> vec ;
	for ( int i = l ; i <= r ; i ++ ) if ( abs( a[i].ff-a[mid].ff ) <= mn ) vec.push_back({ a[i].ss , a[i].ff }) ;
	sort ( vec.begin() , vec.end() ) ;
	for ( int i = 0 ; i < vec.size() ; i ++ ){
		for ( int j = i+1 ; j < vec.size() && vec[j].ff-vec[i].ff < mn ; j ++ ){
			chmin ( ans , dist ( vec[i].ff , vec[i].ss , vec[j].ff , vec[j].ss ) ) ;
		}
	}
	return ans ;
}

void solve(){
	
	cin >> n >> k ;
	for ( int i = 0 ; i < n ; i ++ ) cin >> a[i].ss >> a[i].ff ;
	sort ( a , a + n ) ;
	if ( a[0].ff == a[n-1].ff ){
		for ( int i = 0 ; i < n-1 ; i ++ ){
			st.insert({a[i+1].ss-a[i].ss,{i,i+1}}) ;
		}
		while ( k -- ){
			auto it = *st.begin() ;
			st.erase(st.begin()) ;
			cout << it.ff << endl ;
			if ( it.ss.ss != n-1 ) 
			st.insert({a[it.ss.ss+1].ss-a[it.ss.ff].ss,{it.ss.ff,it.ss.ss+1}}) ;
		}
		return ;
	}
	for ( int i = 0 ; i < n ; i ++ ) swap ( a[i].ff , a[i].ss ) ;
	if ( n <= 5000 ){
		for ( int i = 0 ; i < n ; i ++ ){
			for ( int j = i+1 ; j < n ; j ++ ) ans.push_back(dist(a[i].ff,a[i].ss,a[j].ff,a[j].ss)) ;
		}
		sort ( ans.begin() , ans.end() ) ;
		for ( int i = 0 ; i < k ; i ++ ) cout << ans[i] << '\n' ;
		return ;
	}
	sort ( a , a + n ) ;
	cout << get ( 0 , n-1 ) ;
	 
}

signed main(){
    ios ;
	int t = 1 ;
	//cin >> t ;
	while ( t -- ) solve() ;
}

Compilation message

road_construction.cpp: In function 'long long int get(long long int, long long int)':
road_construction.cpp:75:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for ( int i = 0 ; i < vec.size() ; i ++ ){
      |                    ~~^~~~~~~~~~~~
road_construction.cpp:76:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for ( int j = i+1 ; j < vec.size() && vec[j].ff-vec[i].ff < mn ; j ++ ){
      |                       ~~^~~~~~~~~~~~
road_construction.cpp: In function 'void fopn(std::string)':
road_construction.cpp:10:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:10:72: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 7100 KB Output is correct
2 Correct 63 ms 7092 KB Output is correct
3 Correct 43 ms 5132 KB Output is correct
4 Correct 32 ms 5140 KB Output is correct
5 Correct 47 ms 6100 KB Output is correct
6 Correct 15 ms 6100 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 21396 KB Output is correct
2 Correct 377 ms 21588 KB Output is correct
3 Correct 56 ms 2852 KB Output is correct
4 Correct 173 ms 21176 KB Output is correct
5 Correct 161 ms 21588 KB Output is correct
6 Correct 177 ms 21624 KB Output is correct
7 Correct 176 ms 20876 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 4716 KB Output is correct
2 Correct 124 ms 4716 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 95 ms 20364 KB Output is correct
5 Correct 144 ms 4768 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 4716 KB Output is correct
2 Correct 124 ms 4716 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 95 ms 20364 KB Output is correct
5 Correct 144 ms 4768 KB Output is correct
6 Incorrect 120 ms 4708 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 7100 KB Output is correct
2 Correct 63 ms 7092 KB Output is correct
3 Correct 43 ms 5132 KB Output is correct
4 Correct 32 ms 5140 KB Output is correct
5 Correct 47 ms 6100 KB Output is correct
6 Correct 15 ms 6100 KB Output is correct
7 Incorrect 48 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 7100 KB Output is correct
2 Correct 63 ms 7092 KB Output is correct
3 Correct 43 ms 5132 KB Output is correct
4 Correct 32 ms 5140 KB Output is correct
5 Correct 47 ms 6100 KB Output is correct
6 Correct 15 ms 6100 KB Output is correct
7 Correct 382 ms 21396 KB Output is correct
8 Correct 377 ms 21588 KB Output is correct
9 Correct 56 ms 2852 KB Output is correct
10 Correct 173 ms 21176 KB Output is correct
11 Correct 161 ms 21588 KB Output is correct
12 Correct 177 ms 21624 KB Output is correct
13 Correct 176 ms 20876 KB Output is correct
14 Correct 125 ms 4716 KB Output is correct
15 Correct 124 ms 4716 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 95 ms 20364 KB Output is correct
18 Correct 144 ms 4768 KB Output is correct
19 Incorrect 120 ms 4708 KB Output isn't correct
20 Halted 0 ms 0 KB -