Submission

Score: 80

User: anonymous

Problemset: Weird Castle

Language: cpp

Time: 0.002 second

Submitted On: 2026-10-07 16:04:10

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int n,x; cin >> n >> x;
	bool visit[100000] = {false};
	queue<pair<int, int>> q;
	
	q.push({n, 0});
	visit[n] = true;
	
	while (!q.empty()){
		int room = q.front().first;
		int dist = q.front().second;
		q.pop();
		
		if(room == x){
			cout << dist;
			return 0;
		}
		
		int r = ceil(sqrt(room));
		
		while((r-1) * (r-1) >= room) r--;
		while(r*r < room)r++;
		
		int k = room - (r - 1) * (r - 1);
		
		if(k > 1){
			int next = room - 1;
			if(!visit[next]){
				visit[next] = true;
				q.push({next, dist + 1});
			}
		}
		if(k < 2 * r - 1)
		{
			int next = room + 1;
			
			if(next <= n && !visit[next]){
				visit[next] = true;
				q.push({next, dist + 1});
			}	
		}
		
		if(k%2 == 1){
			int next = r*r+k+1;
			if(next <= n && !visit[next]){
				visit[next] = true;
				q.push({next, dist + 1});
			}	
		}
		else {
			if(r > 1){
				int next = (r-2) * (r-2) + k - 1;
				
				if(next <= n && !visit[next]){
				visit[next] = true;
				q.push({next, dist + 1});
			}
			}
		}
	}
	
}