Submission #350955

#	Time	Username	Problem	Language	Result	Execution time	Memory
350955		Parsa_PG	Spiral (BOI16_spiral)	C++14	0 / 100	1266 ms	52460 KiB

spiral

/* Rastegary Az Shoroe Ye EDAST */
#include <bits/stdc++.h>
     
#define pb push_back
#define endl "\n"
#define ll long long
#define int long long
 
using namespace std;
 
const int maxn =15e3 + 10, Maxn = 1e5 + 10, SQ = 360 , lg = 22 ; 
const int mod = 1e9 + 7;
const ll inf = 1e18 + 10;

int a[maxn][maxn];
int n , like;
bool vis[maxn][maxn];

bool check(int x , int y){
	return x < n && x >= 0 && y < n && y >= 0;
}

pair<int , int> ce(int x , int y){
	if(like == 0){
		if(check(x - 1 , y) && vis[x - 1][y] == 0){
			like++;
			like = like % 4;
			return {x - 1 , y};
		}else{
			if(check(x , y + 1) && vis[x][y + 1] == 0)
				return {x , y + 1};
			else
				return {-1 , -1};
		}
	}
	if(like == 1){
		if(check(x , y - 1) && vis[x][y - 1] == 0){
			like++;
			like = like % 4;
			return {x , y - 1};
		}else{
			if(check(x - 1, y) && vis[x - 1][y] == 0)
				return {x - 1, y};
			else
				return {-1 , -1};
		}
	}
	if(like == 2){
		if(check(x + 1 , y) && vis[x + 1][y] == 0){
			like++;
			like = like % 4;
			return {x + 1, y};
		}else{
			if(check(x , y - 1) && vis[x][y - 1] == 0)
				return {x, y - 1};
			else
				return {-1 , -1};
		}
	}
	if(like == 3){
		if(check(x , y + 1) && vis[x][y + 1] == 0){
			like++;
			like = like % 4;
			return {x , y + 1};
		}else{
			if(check(x + 1, y) && vis[x + 1][y] == 0)
				return {x + 1, y};
			else
				return {-1 , -1};
		}
	}
}

void construct(){
	int i = (n - 1)/2 , j = (n - 1)/2;
	int pt = 1;
	a[i][j] = 1;
	like = 1;
	vis[i][j] = true;
	j++;
	pair<int , int>z;
	while(true){
		pt++;
		vis[i][j] = 1;
		a[i][j] = pt;
		z = ce(i , j);
		if(z.first == -1)
			return;
		i = z.first;
		j = z.second;
	}
}

int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int q;
	cin >> n >> q;
	int nn = n;
	n = 2 * n + 1;
	construct();
	map<int , int>mpx , mpy;
	int pt = nn;
	for(int i = 0 ; i <= nn ; i++){
		mpx[i] = pt; 
		pt--;
	}
	pt = nn + 1;
	for(int i = -1 ; i >= -1 * nn ; i--){
		mpx[i] = pt;
		pt++;
	}
	pt = 0;
	for(int i = -1 * nn ; i <= -1 ; i++){
		mpy[i] = pt;
		pt++;
	}
	for(int i = 0 ; i <= nn ; i++){
		mpy[i] = pt;
		pt++;
	}
	while(q--){
		int x1 , x2 , y1 ,y2;
		cin >> y2 >> x2 >> y1 >> x1;
		int sum = 0;
		for(int i = mpx[x1] ; i <= mpx[x2] ; i++)
			for(int j = mpy[y2] ; j <= mpy[y1] ; j++)
				sum += a[i][j];
		cout << sum << endl;
	}
	return 0;
}

Compilation message (stderr)

spiral.cpp: In function 'std::pair<long long int, long long int> ce(long long int, long long int)':
spiral.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
   72 | }
      | ^

• Subtask 1: 0 / 12
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 31
• Subtask 5: 0 / 25