oj.uz

답안 #893579

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893579 2023-12-27T07:12:00 Z vjudge1 Road Construction (JOI21_road_construction) C++17
18 / 100
 10000 ms 21696 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 , ar ;
	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)) ;//, cout << a[i].ff << ' ' << a[i].ss << endl << a[j].ff << ' ' << a[j].ss << ' ' << dis ( i , j ) << endl ;
		}
		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 ) ;
		ans.push_back(dis(cur.ff,cur.ss)) ;
		cout << dis ( cur.ff , cur.ss ) << endl ;
		//cout << a[cur.ff].ff << ' ' << a[cur.ff].ss << endl ;
		//cout << a[cur.ss].ff << ' ' << a[cur.ss].ss << endl ;
		vis.insert({cur.ff,cur.ss}) ;
	} sort ( ans.begin() , ans.end() ) ;
	//for ( auto i : ans ) cout << i << endl ;
	 
}

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);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp: In function 'std::pair<long long int, long long int> slow(long long int, long long int)':
road_construction.cpp:64:15: warning: 'ar' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |  return {al,ar} ;
      |               ^
road_construction.cpp:64:15: warning: 'al' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 7088 KB Output is correct
2 Correct 53 ms 7100 KB Output is correct
3 Correct 34 ms 5072 KB Output is correct
4 Correct 32 ms 5244 KB Output is correct
5 Correct 49 ms 5820 KB Output is correct
6 Correct 15 ms 5076 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 346 ms 21696 KB Output is correct
2 Correct 348 ms 21372 KB Output is correct
3 Correct 49 ms 2896 KB Output is correct
4 Correct 153 ms 21368 KB Output is correct
5 Correct 151 ms 21584 KB Output is correct
6 Correct 154 ms 21616 KB Output is correct
7 Correct 159 ms 21072 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 4700 KB Output is correct
2 Correct 122 ms 4692 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 92 ms 20304 KB Output is correct
5 Correct 146 ms 4948 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 4700 KB Output is correct
2 Correct 122 ms 4692 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 92 ms 20304 KB Output is correct
5 Correct 146 ms 4948 KB Output is correct
6 Incorrect 584 ms 4740 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 7088 KB Output is correct
2 Correct 53 ms 7100 KB Output is correct
3 Correct 34 ms 5072 KB Output is correct
4 Correct 32 ms 5244 KB Output is correct
5 Correct 49 ms 5820 KB Output is correct
6 Correct 15 ms 5076 KB Output is correct
7 Execution timed out 10029 ms 2920 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 7088 KB Output is correct
2 Correct 53 ms 7100 KB Output is correct
3 Correct 34 ms 5072 KB Output is correct
4 Correct 32 ms 5244 KB Output is correct
5 Correct 49 ms 5820 KB Output is correct
6 Correct 15 ms 5076 KB Output is correct
7 Correct 346 ms 21696 KB Output is correct
8 Correct 348 ms 21372 KB Output is correct
9 Correct 49 ms 2896 KB Output is correct
10 Correct 153 ms 21368 KB Output is correct
11 Correct 151 ms 21584 KB Output is correct
12 Correct 154 ms 21616 KB Output is correct
13 Correct 159 ms 21072 KB Output is correct
14 Correct 122 ms 4700 KB Output is correct
15 Correct 122 ms 4692 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 92 ms 20304 KB Output is correct
18 Correct 146 ms 4948 KB Output is correct
19 Incorrect 584 ms 4740 KB Output isn't correct
20 Halted 0 ms 0 KB -