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 16:07:27100
2016-05-12 12:15:1743
2016-05-12 11:00:0112
Task:Spiral
Sender:geniucos
Submission time:2016-05-12 12:15:17
Language:C++
Status:READY
Score:43

Feedback

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

Test results

testverdicttime (s)group
#1ACCEPTED0.09 / 1.501details
#2WRONG ANSWER0.05 / 1.502details
#3WRONG ANSWER0.05 / 1.503details
#4ACCEPTED0.05 / 1.504details
#5WRONG ANSWER0.04 / 1.505details

Compiler report

input/code.cpp: In function 'void Task1()':
input/code.cpp:143:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &Q);
                     ^
input/code.cpp:147:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d %d %d %d", &a1, &b1, &a2, &b2);
                                                  ^
input/code.cpp: In function 'int main()':
input/code.cpp:159:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &N), mod = 1e9 + 7;
                                ^
input/code.cpp:165:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &Q);
                 ^
input/code.cpp:169:46: warning: ignoring return value of '

Code

#include<bits/stdc++.h>

using namespace std;

int mod, N, Q, nr, a[2016][2016], s[2016][2016];

void Move (int steps, int dx, int dy, int &i, int &j)
{
    while (steps --) i += dx, j += dy, a[i][j] = ++nr;
}

void Print ()
{
    for (int i=1; i<=2 * N + 1; i++, printf ("\n"))
        for (int j=1; j<=2 * N + 1; j++)
            printf ("%2d ", a[i][j]);
    printf ("\n");
}

int sum (int a1, int b1, int a2, int b2)
{
    int ans = (s[a2][b2] - s[a1 - 1][b2] - s[a2][b1 - 1] + s[a1 - 1][b1 - 1]) % mod;
    if (ans < 0) ans += mod;
    return ans;
}

int pow (int a, int b, int mod)
{
    int p = 1;
    for (int i=0; (1<<i) <= b; i++)
    {
        if (b & (1 << i)) p = (1LL * p * a) % mod;
        a = (1LL * a * a) % mod;
    }
    return p;
}

int Gs1 (int i)
{
    return (1LL * i * (i + 1) / 2) % mod;
}

int Gs2 (int x)
{
    int v[3];
    v[0] = x, v[1] = x + 1, v[2] = 2 * x + 1;
    for (int j=2; j<=3; j++)
        for (int i=0; i<3; i++)
            if (v[i] % j == 0)
            {
                v[i] /= j;
                break;
            }
    return (1LL * ((1LL * v[0] * v[1]) % mod) * v[2]) % mod;
}

int Gs3 (int x)
{
    x = Gs1 (x);
    return (1LL * x * x) % mod;
}

int gs1 (int st, int dr)
{
    int ans = Gs1 (dr) - Gs1 (st - 1);
    if (ans < 0) ans += mod;
    return ans;
}

int gs2 (int st, int dr)
{
    int ans = Gs2 (dr) - Gs2 (st - 1);
    if (ans < 0) ans += mod;
    return ans;
}

int gs3 (int st, int dr)
{
    int ans = Gs3 (dr) - Gs3 (st - 1);
    if (ans < 0) ans += mod;
    return ans;
}

int s1 (int i)
{
    int ans = (2LL * i * i) % mod;
    ans = (1LL * ans * (i + 1)) % mod;
    ans = (1LL * ans * (i + 1) + i + 1) % mod;
    return ans;
}

int sum_pol (int st, int dr, int A, int B, int C)
{
    ///sum for k = st, dr Ak ^ 2 + Bk + C
    int ans = (1LL * A * gs2 (st, dr) + 1LL * B * gs1 (st, dr) + 1LL * C * (dr - st + 1)) % mod;
    if (ans < 0) ans += mod;
    return ans;
}

int sum1 (int i, int j)
{
    if (i < 0 || j < 0) return 0;
    if (i >= j)
    {
        int curr1 = s1 (j), curr2 = 1LL * j * (i - j) % mod, curr3 = (2LL * sum_pol (j + 1, i, 4, -3, 1)) % mod;
        curr2 += curr3;
        if (curr2 >= mod) curr2 -= mod;
        curr2 = (1LL * curr2 * (j + 1)) % mod;
        if (curr2 % 2 == 0) curr2 /= 2;
        else curr2 = (curr2 + mod) / 2;
        curr1 += curr2;
        if (curr1 >= mod) curr1 -= mod;
        return curr1;
    }
    int curr1 = s1 (i), curr2 = mod - 1LL * i * (j - i) % mod, curr3 = (2LL * sum_pol (i + 1, j, 4, -1, 1)) % mod;
    curr2 += curr3;
    if (curr2 >= mod) curr2 -= mod;
    curr2 = (1LL * curr2 * (i + 1)) % mod;
    if (curr2 % 2 == 0) curr2 /= 2;
    else curr2 = (curr2 + mod) / 2;
    curr1 += curr2;
    if (curr1 >= mod) curr1 -= mod;
    return curr1;
}

void Task1 ()
{
    a[N + 1][N + 1] = nr = 1;
    for (int l = 1; l <= N; l++)
    {
        int i = N + l + 1, j = i;
        Move (2 * l, -1, 0, i, j);
        Move (2 * l, 0, -1, i, j);
        Move (2 * l, 1, 0, i, j);
        Move (2 * l, 0, 1, i, j);
    }
    for (int i=1; i<=2 * N + 1; i++)
        for (int j=1; j<=2 * N + 1; j++)
        {
            s[i][j] = (s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]) % mod;
            if (s[i][j] < 0) s[i][j] += mod;
        }
    scanf ("%d", &Q);
    while (Q --)
    {
        int a1, b1, a2, b2;
        scanf ("%d %d %d %d", &a1, &b1, &a2, &b2);
        a1 += N + 1, b1 += N + 1, a2 += N + 1, b2 += N + 1;
        swap (a1, b1), swap (a2, b2); a1 = 2 * N + 1 - a1 + 1, a2 = 2 * N + 1 - a2 + 1, swap (a1, a2);
        printf ("%d\n", sum (a1, b1, a2, b2));
    }
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d", &N), mod = 1e9 + 7;
if (N <= 2000)
{
    Task1 ();
    return 0;
}
scanf ("%d", &Q);
while (Q --)
{
    int a1, b1, a2, b2, ans;
    scanf ("%d %d %d %d", &a1, &b1, &a2, &b2);
    ans = (sum1 (a2, b2) - sum1 (a1 - 1, b2) - sum1 (a2, b1 - 1) + sum1 (a1 - 1, b1 - 1)) % mod;
    if (ans < 0) ans += mod;
    printf ("%d\n", ans);
}
//Print ();
/*int curr = 0, curr2;
for (int i=0; i<=N; i++)
{
    curr += (4 * i * i - 2 * i + 1) * (2 * i + 1);
    curr2 = 2 * i * i * (i + 1) * (i + 1) + i + 1;
    printf ("%d %d %d\n", sum (N + 1 - i, N + 1, N + 1, N + i + 1), curr, curr2);
}*/
/*for (int i=0; i<=N; i++)
    for (int j=0; j<=N; j++)
        printf ("%d %d -> %d %d\n", i, j, sum1 (i, j), sum (N + 1 - j, N + 1, N + 1, N + 1 + i));
return 0;*/
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: WRONG ANSWER

input
1000000000 100
181053719 1000000000 181053719...
view   save

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

user output
818946492
750635163
0
0
0
...
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
0
826975265
0
18263594
915389070
...
view   save

Test 4

Group: 4

Verdict: ACCEPTED

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
695961158
957360176
137575768
522232140
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
0
0
239483569
113507818
278402948
...
view   save