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 12:33:44
Language:C++
Status:READY
Score:27

Feedback

groupverdictscore
#1ACCEPTED12
#2ACCEPTED15
#3WRONG ANSWER0
#4WRONG ANSWER0
#5WRONG ANSWER0

Test results

testverdicttime (s)group
#1ACCEPTED0.16 / 1.501details
#2ACCEPTED0.05 / 1.502details
#3WRONG ANSWER0.04 / 1.503details
#4WRONG ANSWER0.05 / 1.504details
#5WRONG ANSWER0.05 / 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;
}

ll modpow(ll a, ll b)
{
	ll r = 1;
	while(b)
	{
		if(b&1) r = (r*a)%MOD;
		a = (a*a)%MOD;
		b >>= 1;
	}
	if(r < 0) r += MOD;
	return r;
}

ll inv(ll x)
{
	return modpow(x, MOD - 2);
}

ll inv2, inv6, inv12;

ll mult(ll a, ll b)
{
	a %= MOD; b %= MOD;
	if(a < 0) a += MOD;
	if(b < 0) b += MOD;
	ll ans = (a*b)%MOD;
	if(ans < 0) ans += MOD;
	return ans;
}

ll sum(ll x)
{
	ll res = mult(x, mult(x + 1, inv2));
	return res;
}

ll sum2(ll x)
{
	ll res = mult(x, mult(x + 1, mult(2*x + 1, inv6)));
	return res;
}

ll sum3(ll x)
{
	ll res = mult(x, mult(x - 1, mult(x + 1, inv6)));
	return res;
}

ll sum4(ll x)
{
	ll res = mult(x, mult(x, mult(x - 1, mult(x + 1, inv12))));
	return res;
}

ll sub4(ll x, ll y)
{
	ll res = 0;
	ll a, b, c;
	if(y <= x)
	{
		c = (mult(sum(y + 1) - 1, x) + sum3(y))%MOD;
		b = (mult(sum(x), y) + sum3(y))%MOD;
		a = (mult(sum2(y), y) + sum4(y))%MOD;
	}
	else
	{
		c = (mult(sum(x + 1) - 1, x) + sum3(x))%MOD;
		b = (mult(sum(x), x) + sum3(x))%MOD;
		a = (mult(sum2(x), x) + sum4(x))%MOD;
		ll a2, b2, c2;
		c2 = (mult(mult(sum(y) - sum(x), x), 2LL) - mult(y - x, sum(x - 1)))%MOD;
		b2 = mult(sum(y) - sum(x), x);
		a2 = mult(sum2(y) - sum2(x), x);
		c = (c + c2)%MOD;
		b = (b + b2)%MOD;
		a = (a + a2)%MOD;
	}
	res = mult(a, 4LL) - mult(b, 3LL) + c;
	res %= MOD;
	if(res < 0) res += MOD;
	return res;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>q;
	inv2 = inv(2);
	inv6 = inv(6);
	inv12 = inv(12);
	if(n <= 1000)
	{
		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 if(n > 1000)
		{
			cout << sub4(x2, y2) << '\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: ACCEPTED

input
1000000000 100
181053719 1000000000 181053719...
view   save

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

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

Test 3

Group: 3

Verdict: WRONG ANSWER

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
152229513
701177838
657530887
674668865
283993964
...
view   save

Test 4

Group: 4

Verdict: WRONG ANSWER

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
207033743
506204293
249069989
481470434
58884045
...
view   save

Test 5

Group: 5

Verdict: WRONG ANSWER

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

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

user output
402324961
172742262
343265828
884007446
945175452
...
view   save