|
| 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
Task: | Spiral |
Sender: | zscoder |
Submission time: | 2016-05-12 11:40:49 |
Language: | C++ |
Status: | READY |
Score: | 12 |
Feedback
group | verdict | score |
#1 | ACCEPTED | 12 |
#2 | RUNTIME ERROR | 0 |
#3 | TIME LIMIT EXCEEDED | 0 |
#4 | RUNTIME ERROR | 0 |
#5 | RUNTIME ERROR | 0 |
Test results
test | verdict | time (s) | group | |
#1 | ACCEPTED | 0.16 / 1.50 | 1 | details |
#2 | RUNTIME ERROR | 0.28 / 1.50 | 2 | details |
#3 | TIME LIMIT EXCEEDED | -- / 1.50 | 3 | details |
#4 | RUNTIME ERROR | 0.28 / 1.50 | 4 | details |
#5 | RUNTIME ERROR | 0.29 / 1.50 | 5 | details |
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 ...
|
correct output |
---|
788057008 633127082 507903329 53165899 558016315 ...
|
user output |
---|
788057008 633127082 507903329 53165899 558016315 ...
|
Test 2
Group: 2
Verdict: RUNTIME ERROR
input |
---|
1000000000 100 181053719 1000000000 181053719...
|
correct output |
---|
818946492 750635163 193830026 660632411 46072376 ...
|
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 ...
|
correct output |
---|
986592951 708386765 85336595 18263594 32233727 ...
|
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 ...
|
correct output |
---|
695961158 957360176 137575768 522232140 58884045 ...
|
Test 5
Group: 5
Verdict: RUNTIME ERROR
input |
---|
1000000000 100 -857489445 -1000000000 -432836...
|
correct output |
---|
902627632 581519884 819269364 857298983 278402948 ...
|