제출 #30700

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30700		noobprogrammer	Spiral (BOI16_spiral)	C++14	12 / 100	136 ms	33424 KiB

spiral

#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
#define ii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vii vector<ii>
inline ll sqr(ll x) { return x*x ; } 

const ll mod = 1e9 + 7 ;
int n , q ;
ll qs[2005][2005] ;
int dx[] = {1 , 0 , -1 , 0} , dy[] = {0 , -1 , 0 , 1} ;

void fill_table(int x , int y , ll k ){
	qs[y+n+1][x+n+1] = k ; 
	if( x == -y && sqr(2*abs(x)+1) == k ){
		if(x == n) return ;
		fill_table(x+1 , y , k+1 );
		return ;
	}
	if( sqr(2*(max( abs(x),abs(y))-1) + 1) == k-1 ){
		fill_table(x , y+1 , k+1) ;
		return ;
	}
		
	int nx , ny ;
	for(int i=0;i<4;i++){
		nx = x + dx[i] ; ny = y + dy[i] ;
		if(qs[ny + n + 1][nx + n + 1] > 0 ) continue ;
		if( max(abs(nx) , abs(ny)) != max( abs(x),abs(y)) ) continue ;
		fill_table(nx , ny , k+1) ;
		return ;
	}
}

int main(){
	// freopen("in.txt" ,"r" , stdin ) ;
	scanf("%d%d",&n,&q) ;
	fill_table(0 , 0 , 1) ;
	/*for(int i=1;i<=2*n+1;i++) {
		for(int j=1;j<=2*n+1;j++) printf("%lld " , qs[i][j]) ;
		cout<<endl;
	}*/
	for(int i=1;i<=2*n+1;i++) 
		for(int j=1;j<=2*n+1;j++) qs[i][j] += (qs[i][j-1] + qs[i-1][j] - qs[i-1][j-1]) , 
		qs[i][j]%=mod ;
	int x1 , x2 , y1 , y2 ; 
	for(int i=0 ; i<q ; i++){
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2) ;
		x1 += n+1 ; y1 += n+1 ; x2 += n+1 ; y2 += n+1 ;
		printf("%lld\n" , ( (qs[y2][x2] - qs[y2][x1-1] - qs[y1-1][x2] + qs[y1-1][x1-1])%mod + mod )%mod  ) ;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

spiral.cpp: In function 'int main()':
spiral.cpp:40:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&q) ;
                      ^
spiral.cpp:51:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d",&x1,&y1,&x2,&y2) ;
                                     ^

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