Submission #28431

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
28431	2017-07-16T05:48:03 Z	ㅁㄴㅇㄹ호(#1227, gs13105)	Oriental P.A.D.A.K (FXCUP2_padak)	C++14	0 / 1	79 ms	65536 KB

padak

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

using namespace std;

struct pos
{
    int x, y;
};

queue<pos> q;
vector<bool> chk[1000000];
vector<int> arr;
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);

    for(i = 0; i<n; i++)
        chk[i] = vector<bool>(m, 0);

    for(i = 0; i<k; i++)
    {
        scanf("%d%d", &x, &y);
        x--;
        y--;
        chk[x][y] = 1;
        q.push({ x, y });
    }

    for(c = 1; !q.empty(); c++)
    {
        s = q.size();
        for(i = 0; i<s; i++)
        {
            x = q.front().x;
            y = q.front().y;
            q.pop();

            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][ny])
                    continue;

                chk[nx][ny] = 1;
                arr.push_back(c);
                q.push({ nx, ny });
            }
        }
    }

    sort(arr.begin(), arr.end());

    int r1 = 0, r2 = 0;
    int p = 0, as = (int)arr.size();
    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

padak.cpp: In function 'int main()':
padak.cpp:30: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:37: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

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	40996 KB	Output is correct
2	Correct	13 ms	40996 KB	Output is correct
3	Correct	66 ms	47372 KB	Output is correct
4	Correct	79 ms	47364 KB	Output is correct
5	Correct	63 ms	47352 KB	Output is correct
6	Correct	59 ms	50348 KB	Output is correct
7	Correct	56 ms	47348 KB	Output is correct
8	Correct	49 ms	47348 KB	Output is correct
9	Memory limit exceeded	43 ms	65536 KB	Memory limit exceeded
10	Halted	0 ms	0 KB	-