Code Submission Evaluation System Login

BOI 2016, day 1

Start:2016-05-12 09:00:00
End:2016-05-12 14:00:00
 

Tasks | Scoreboard | Statistics


CSES - BOI 2016, day 1 - Results
History
2016-05-12 13:57:2731
2016-05-12 13:51:3531
2016-05-12 13:50:4531
2016-05-12 12:55:5358
2016-05-12 12:44:1627
2016-05-12 12:43:5115
2016-05-12 12:42:5215
2016-05-12 12:33:4427
2016-05-12 11:42:4927
2016-05-12 11:40:4912
2016-05-12 11:25:1815
Task:Spiral
Sender:zscoder
Submission time:2016-05-12 11:40:49
Language:C++
Status:READY
Score:12

Feedback

groupverdictscore
#1ACCEPTED12
#2RUNTIME ERROR0
#3TIME LIMIT EXCEEDED0
#4RUNTIME ERROR0
#5RUNTIME ERROR0

Test results

testverdicttime (s)group
#1ACCEPTED0.16 / 1.501details
#2RUNTIME ERROR0.28 / 1.502details
#3TIME LIMIT EXCEEDED-- / 1.503details
#4RUNTIME ERROR0.28 / 1.504details
#5RUNTIME ERROR0.29 / 1.505details

Compiler report

input/code.cpp: In function 'll singlesquare(ll, ll)':
input/code.cpp:75:12: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  res %= MOD;
            ^

Code

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef pair<ii, ll> iii;

const int MOD = 1e9 + 7;

ll abso(ll y)
{
	if(y < 0) return -y;
	return y;
}
ll n, q; 
ll dp[2011][2011];
ll spiral[2011][2011];

ll singlesquare(ll x, ll y)
{
	ll res;
	if(x == 0 && y == 0) return 1;
	if(x == 0 && y > 0)
	{
		res = 4*y*y - y + 1;
	}
	else if(x == 0 && y < 0)
	{
		res = 4*y*y - 3*y + 1;
	}
	else if(x > 0 && y == 0)
	{
		res = 4*x*x - 3*x + 1;
	}
	else if(x < 0 && y == 0)
	{
		res = 4*x*x - x + 1;
	}
	else
	{
		ll layer = max(abso(x), abso(y));
		if(abso(y) == layer)
		{
			res = singlesquare(0, y);
			//cout << res << endl;
			if(y > 0)
			{
				res -= x;
			}
			else
			{
				res += x;
			}
		}
		else if(abso(x) == layer)
		{
			res = singlesquare(x, 0);
			if(x > 0)
			{
				res += y;
			}
			else
			{
				res -= y;
			}
		}
	}
	res %= MOD;
	if(res < 0) res += MOD;
	return res;
}

void fillspiral()
{
	for(int i = 1; i <= 2*n + 1; i++)
	{
		for(int j = 1; j <= 2*n + 1; j++)
		{
			spiral[i][j] = singlesquare(i - n - 1, j - n - 1);
		}
	}
	/*
	for(int i = 2*n + 1; i >= 1; i--)
	{
		for(int j = 1; j <= 2*n + 1; j++)
		{
			cout << spiral[j][i] << ' ';
		}
		cout << '\n';
	}
	*/
}

void filldp()
{
	for(int i = 1; i <= 2*n + 1; i++)
	{
		for(int j = 1; j <= 2*n + 1; j++)
		{
			if(i == 1 && j == 1) dp[i][j] = spiral[i][j];
			else if(i == 1)
			{
				dp[i][j] = (dp[i][j - 1] + spiral[i][j])%MOD;
			}
			else if(j == 1)
			{
				dp[i][j] = (dp[i - 1][j] + spiral[i][j])%MOD;
			}
			else
			{
				dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + spiral[i][j])%MOD;
				if(dp[i][j] < 0) dp[i][j] += MOD;
			}
		}
	}
	/*
	for(int i = 2*n + 1; i >= 1; i--)
	{
		for(int j = 1; j <= 2*n + 1; j++)
		{
			cout << dp[j][i] << ' ';
		}
		cout << '\n';
	}
	*/
}

ll rec(ll x1, ll y1, ll x2, ll y2)
{
	ll res = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
	res %= MOD;
	if(res < 0) res += MOD;
	return res;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>q;
	fillspiral();
	filldp();
	for(int i = 0; i < q; i++)
	{
		ll x1, x2, y1, y2;
		cin>>x1>>y1>>x2>>y2;
		if(x1 == x2 && y1 == y2) cout << singlesquare(x1,y1) << '\n';
		else
		{
			x1 += (n+1);
			y1 += (n+1);
			x2 += (n+1);
			y2 += (n+1);
			cout << rec(x1, y1, x2, y2) << '\n';
		}
	}
	return 0;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
1000 100
-709 0 1000 123
-621 -1000 -102 -435
-602 -560 276 -356
-945 -590 0 -468
...
view   save

correct output
788057008
633127082
507903329
53165899
558016315
...
view   save

user output
788057008
633127082
507903329
53165899
558016315
...
view   save

Test 2

Group: 2

Verdict: RUNTIME ERROR

input
1000000000 100
181053719 1000000000 181053719...
view   save

correct output
818946492
750635163
193830026
660632411
46072376
...
view   save

user output
(empty)

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
100000 100
-88233 -87279 -49871 52277
-86645 -7997 48948 30702
-79916 -36210 -21257 -16821
0 57331 93163 100000
...
view   save

correct output
986592951
708386765
85336595
18263594
32233727
...
view   save

user output
(empty)

Test 4

Group: 4

Verdict: RUNTIME ERROR

input
1000000000 100
1 1 21134200 719983102
1 1 929463279 1000000000
1 1 68450838 1
1 1 84417340 297177199
...
view   save

correct output
695961158
957360176
137575768
522232140
58884045
...
view   save

user output
(empty)

Test 5

Group: 5

Verdict: RUNTIME ERROR

input
1000000000 100
-857489445 -1000000000 -432836...
view   save

correct output
902627632
581519884
819269364
857298983
278402948
...
view   save

user output
(empty)