Submission #28449

#	Time	Username	Problem	Language	Result	Execution time	Memory
28449		ㅁㄴㅇㄹ호 (#68)	Oriental P.A.D.A.K (FXCUP2_padak)	C++14	1 / 1	399 ms	13816 KiB

padak

#include <stdio.h>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <tuple>

using namespace std;

int qx[1000000];
int qy[1000000];

bool chk[1000000];

int arr[1000000];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int main()
{
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);

    int n, m, k, z, x, y, nx, ny, s, c, i, j;
    scanf("%d%d%d%*d%d", &n, &m, &k, &z);

    int as = 0;
    int qs = 0, qg = 0;
    const int siz = 1000000;

    for(i = 0; i<k; i++)
    {
        scanf("%d%d", &x, &y);
        x--;
        y--;
        if(chk[x*m + y])
            continue;
        chk[x*m + y] = 1;
        qx[qg%siz] = x;
        qy[qg%siz] = y;
        qg++;
    }

    for(c = 1; qs < qg; c++)
    {
        s = qg - qs;
        for(i = 0; i<s; i++)
        {
            x = qx[qs%siz];
            y = qy[qs%siz];
            qs++;

            for(j = 0; j<4; j++)
            {
                nx = x + dx[j];
                ny = y + dy[j];

                if(nx<0 || nx>=n || ny<0 || ny>=m || chk[nx*m + ny])
                    continue;

                chk[nx*m + ny] = 1;
                arr[as++] = c;

                qx[qg%siz] = nx;
                qy[qg%siz] = ny;
                qg++;
            }
        }
    }

    sort(arr, arr + as);

    int r1 = 0, r2 = 0;
    int p = 0;
    for(i = 1;; i++)
    {
        while(p != as && arr[p] < i)
            p++;

        if(p == as)
            break;

        r1 += min(z, as - p);
        p += min(z, as - p);
    }

    p = as - 1;
    for(i = 1;; i++)
    {
        
        for(j = 0; j<z; j++)
        {
            if(p == -1 || arr[p] < i)
                break;

            r2++;
            p--;
        }

        if(p == -1 || arr[p] < i)
            break;
    }

    printf("%d %d\n", r2, r1);
    return 0;
}

Compilation message (stderr)

padak.cpp: In function 'int main()':
padak.cpp:27:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%*d%d", &n, &m, &k, &z);
                                         ^
padak.cpp:35:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
                              ^

• Subtask 1: 1 / 1