oj.uz

Submission #893811

# Submission time Handle Problem Language Result Execution time Memory
893811 2023-12-27T13:22:04 Z Cutebol Road Construction (JOI21_road_construction) C++17
18 / 100
 10000 ms 21536 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 ;
set <pii> vis ;

int dist ( int x , int y , int x1 , int y1 ){
	return abs(x-x1)+abs(y-y1) ;
}
int dis ( int i  , int j ){
	return dist ( a[i].ff , a[i].ss , a[j].ff , a[j].ss ) ;
}
pii slow ( int l , int r ){
	int res = inf , al = l , ar = r ;
	for ( int i = l ; i <= r ; i ++ ){
		for ( int j = i+1 ; j <= r ; j ++ ) if ( vis.find({i,j}) == vis.end() && chmin ( res , dis( i , j ) ) ) al = i , ar = j ;
	}
	return {al,ar} ;
}
pii get ( int l , int r ){
	
	if ( r - l + 1 < 5 ) return slow(l,r) ;
	int mid = ( l + r ) / 2 ;
	pii ml = get ( l , mid ) ;
	pii mr = get ( mid+1 , r ) ;
	int mn = min ( dis( ml.ff , ml.ss )  , dis( mr.ff , mr.ss ) ) ;
	int ans = mn , al = ml.ff , ar = ml.ss ;
	if ( mn < dis ( ml.ff , ml.ss ) ) al = mr.ff , ar = mr.ss ;
	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 , i }) ;
	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 ++ ){
			if ( vis.find({vec[i].ss,vec[j].ss}) == vis.end() && chmin ( ans , dis ( vec[i].ss , vec[j].ss  ) ) ) al = vec[i].ss , ar = vec[j].ss ;
		}
	}
	
	return {al,ar} ;
}

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 ) ;
	for ( int i = 0 ; i < k ; i ++ ){
		pii cur = get ( 0 , n-1 ) ;
		cout << dis ( cur.ff , cur.ss ) << endl ;
		vis.insert({cur.ff,cur.ss}) ;
	}
}

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

Compilation message

road_construction.cpp: In function 'std::pair<long long int, long long int> get(long long int, long long int)':
road_construction.cpp:78: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]
   78 |  for ( int i = 0 ; i < vec.size() ; i ++ ){
      |                    ~~^~~~~~~~~~~~
road_construction.cpp:79: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]
   79 |   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 52 ms 7096 KB Output is correct
2 Correct 52 ms 7104 KB Output is correct
3 Correct 33 ms 5064 KB Output is correct
4 Correct 32 ms 5064 KB Output is correct
5 Correct 49 ms 5824 KB Output is correct
6 Correct 15 ms 5332 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 21452 KB Output is correct
2 Correct 332 ms 21536 KB Output is correct
3 Correct 51 ms 2896 KB Output is correct
4 Correct 150 ms 21328 KB Output is correct
5 Correct 183 ms 21512 KB Output is correct
6 Correct 151 ms 21436 KB Output is correct
7 Correct 185 ms 20644 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 4692 KB Output is correct
2 Correct 126 ms 4700 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 95 ms 20328 KB Output is correct
5 Correct 142 ms 4772 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 4692 KB Output is correct
2 Correct 126 ms 4700 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 95 ms 20328 KB Output is correct
5 Correct 142 ms 4772 KB Output is correct
6 Incorrect 594 ms 4724 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 7096 KB Output is correct
2 Correct 52 ms 7104 KB Output is correct
3 Correct 33 ms 5064 KB Output is correct
4 Correct 32 ms 5064 KB Output is correct
5 Correct 49 ms 5824 KB Output is correct
6 Correct 15 ms 5332 KB Output is correct
7 Execution timed out 10037 ms 2700 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 7096 KB Output is correct
2 Correct 52 ms 7104 KB Output is correct
3 Correct 33 ms 5064 KB Output is correct
4 Correct 32 ms 5064 KB Output is correct
5 Correct 49 ms 5824 KB Output is correct
6 Correct 15 ms 5332 KB Output is correct
7 Correct 318 ms 21452 KB Output is correct
8 Correct 332 ms 21536 KB Output is correct
9 Correct 51 ms 2896 KB Output is correct
10 Correct 150 ms 21328 KB Output is correct
11 Correct 183 ms 21512 KB Output is correct
12 Correct 151 ms 21436 KB Output is correct
13 Correct 185 ms 20644 KB Output is correct
14 Correct 125 ms 4692 KB Output is correct
15 Correct 126 ms 4700 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 95 ms 20328 KB Output is correct
18 Correct 142 ms 4772 KB Output is correct
19 Incorrect 594 ms 4724 KB Output isn't correct
20 Halted 0 ms 0 KB -