oj.uz

답안 #1072849

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1072849 2024-08-24T05:47:45 Z emptypringlescan Building Skyscrapers (CEOI19_skyscrapers) C++17
0 / 100
 9 ms 2648 KB 
#include <bits/stdc++.h>
using namespace std;
struct custom_hash{
	size_t operator()(pair<long long,long long> x) const{
		return x.first*(1e9+5)+x.second;
	}
};
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
vector<int> adj[1500];
int v[1500];
int dfs(int x){
	v[x]=1;
	int ret=1;
	for(int i:adj[x]) if(!v[i]) ret+=dfs(i);
	return ret;
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,t;
	cin >> n >> t;
	pair<pair<int,int>,int> arr[n];
	for(int i=0; i<n; i++){
		cin >> arr[i].first.first >> arr[i].first.second;
		arr[i].second=i;
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(abs(arr[i].first.first-arr[j].first.first)<=1&&abs(arr[i].first.second-arr[j].first.second)<=1){
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
		}
	}
	if(dfs(0)!=n){
		cout << "NO";
		return 0;
	}
	mt19937 rng(999);
	shuffle(arr,arr+n,rng);
	do{
		bool can=true;
		unordered_set<pair<int,int>,custom_hash> got;
		for(int i=0; i<n; i++){
			bool nxt=false;
			if(!i) nxt=true;
			for(int j=0; j<i; j++){
				if(abs(arr[i].first.first-arr[j].first.first)<=1&&abs(arr[i].first.second-arr[j].first.second)<=1) nxt=true;
			}
			if(!nxt) can=false;
			if(!can) break;
			got.clear();
			for(int j=0; j<i; j++) got.insert(arr[j].first);
			queue<pair<int,int> > q;
			q.push(arr[i].first);
			while(!q.empty()){
				pair<int,int> x=q.front();
				q.pop();
				if(got.find(x)!=got.end()) continue;
				got.insert(x);
				if(abs(arr[i].first.first-x.first)+abs(arr[i].first.second-x.second)>n/2) break;
				for(int j=0; j<4; j++){
					pair<int,int> nx={x.first+dx[j],x.second+dy[j]};
					if(got.find(nx)==got.end()) q.push(nx);
				}
			}
			while(!q.empty()) q.pop();
		}
		if(can){
			cout << "YES\n";
			for(int i=0; i<n; i++) cout << arr[i].second+1 << ' ';
			return 0;
		}
	} while(next_permutation(arr+1,arr+n));
	assert(false);
	cout << "NO";
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ans=YES N=1
2 Correct 0 ms 348 KB ans=YES N=4
3 Correct 0 ms 348 KB ans=NO N=4
4 Correct 0 ms 344 KB ans=YES N=5
5 Correct 1 ms 344 KB ans=YES N=9
6 Incorrect 0 ms 348 KB Added cell 5 (0,0) not reachable from infinity
7 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ans=YES N=1
2 Correct 0 ms 348 KB ans=YES N=4
3 Correct 0 ms 348 KB ans=NO N=4
4 Correct 0 ms 344 KB ans=YES N=5
5 Correct 1 ms 344 KB ans=YES N=9
6 Incorrect 0 ms 348 KB Added cell 5 (0,0) not reachable from infinity
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ans=YES N=1
2 Correct 0 ms 348 KB ans=YES N=4
3 Correct 0 ms 348 KB ans=NO N=4
4 Correct 0 ms 344 KB ans=YES N=5
5 Correct 1 ms 344 KB ans=YES N=9
6 Incorrect 0 ms 348 KB Added cell 5 (0,0) not reachable from infinity
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ans=YES N=1
2 Correct 0 ms 348 KB ans=YES N=4
3 Correct 0 ms 348 KB ans=NO N=4
4 Correct 0 ms 344 KB ans=YES N=5
5 Correct 1 ms 344 KB ans=YES N=9
6 Incorrect 0 ms 348 KB Added cell 5 (0,0) not reachable from infinity
7 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 2648 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -