CSES - Datatähti 2022 alku - Results
Submission details
Task:Spiraali (Spiral)
Sender:wolruso
Submission time:2021-10-10 20:00:20
Language:C++11
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED15
#2ACCEPTED20
#3ACCEPTED65
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1details
#2ACCEPTED0.01 s2details
#3ACCEPTED0.01 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lu %lu", &size, &testCount);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lu %lu", &tests[i].y, &tests[i].x);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp: In function 'uint64_t getValue(uint64_t, uint64_t, uint64_t)':
input/code.cpp:60:32: warning: 'sideStartingValue' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return sideStartingValue + sideRelativeCoord;
                                ^~~~~~~~~~~~~~~~~
input/code.cpp:60:32: warning: 'sideRelativeCoord' may be used uninitialized in this function [-Wmaybe-uninitialized]

Code

#include <stdio.h>
#include <stdint.h>

struct Test
{
    uint64_t x;
    uint64_t y;
};

uint64_t getValue(uint64_t x, uint64_t y, uint64_t size)
{
    // Quit if invalid coordinates
    if (x >= size || y >= size)
        return 0;
    uint64_t ringDepth, ringSize, ringRelativeX, ringRelativeY, sideRelativeCoord;
    uint64_t ringStartingValue, sideStartingValue;
    const uint64_t maxIndx = size - 1;

    // Calculate the ring depth
    ringDepth = x;
    if (y < ringDepth) ringDepth = y;
    if (maxIndx - x < ringDepth) ringDepth = maxIndx - x;
    if (maxIndx - y < ringDepth) ringDepth = maxIndx - y;

    // Calculate the size of the ring and the coordinates relative to it
    ringSize = size - ringDepth * 2;
    ringRelativeX = x - ringDepth;
    ringRelativeY = y - ringDepth;

    /**
     * n = ringDepth
     * o = order of matrix
     * ringStartingValue = 1 + 4n(o - n)
     */
    // Calculate the starting value of the ring
    ringStartingValue = 1 + 4 * ringDepth * (size - ringDepth);

    // Calculate the side of this ring, it's starting value and the coordinate relative to it
    if (ringRelativeX == 0)
    {
        sideStartingValue = ringStartingValue + 0 * (ringSize - 1);
        sideRelativeCoord = ringRelativeY;
    }
    else if (ringRelativeY == ringSize - 1)
    {
        sideStartingValue = ringStartingValue + 1 * (ringSize - 1);
        sideRelativeCoord = ringRelativeX;
    }
    else if (ringRelativeX == ringSize - 1)
    {
        sideStartingValue = ringStartingValue + 2 * (ringSize - 1);
        sideRelativeCoord = (ringSize - 1) - ringRelativeY;
    }
    else if (ringRelativeY == 0)
    {
        sideStartingValue = ringStartingValue + 3 * (ringSize - 1);
        sideRelativeCoord = (ringSize - 1) - ringRelativeX;
    }

    return sideStartingValue + sideRelativeCoord;
}

int main()
{
    uint64_t size;
    uint64_t testCount;
    scanf("%lu %lu", &size, &testCount);
    Test *tests = new Test[testCount];
    for (uint64_t i = 0; i < testCount; i++)
    {
        scanf("%lu %lu", &tests[i].y, &tests[i].x);
        // Map the indices from the range [1, n] to [0, n - 1]
        tests[i].y--;
        tests[i].x--;
    }
    for (uint64_t i = 0; i < testCount; i++)
    {
        printf("%lu\n", getValue(tests[i].x, tests[i].y, size));
    }
    return 0;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
10 100
1 1
1 2
1 3
1 4
...

correct output
1
36
35
34
33
...

user output
1
36
35
34
33
...

Test 2

Group: 2

Verdict: ACCEPTED

input
1000 1000
371 263
915 322
946 880
53 738
...

correct output
773533
312166
206053
200080
593922
...

user output
773533
312166
206053
200080
593922
...

Test 3

Group: 3

Verdict: ACCEPTED

input
1000000000 1000
177757853 827347032
409613589 419171337
739269360 256524697
328695530 896842209
...

correct output
571375684522141210
967321186816598569
762879105851175000
370065046779516790
936897883750373771
...

user output
571375684522141210
967321186816598569
762879105851175000
370065046779516790
936897883750373771
...