oj.uz

Submission #28444

# Submission time Handle Problem Language Result Execution time Memory
28444 2017-07-16T06:00:35 Z ㅁㄴㅇㄹ호(#1227, gs13105) Oriental P.A.D.A.K (FXCUP2_padak) C++14
0 / 1
 43 ms 65536 KB 
#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];

vector<vector<bool>> chk;
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);

    chk = vector<vector<bool>>(n, vector<bool>(m, 0));

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

                chk[nx][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

padak.cpp: In function 'int main()':
padak.cpp:26: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:36: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 0 ms 13652 KB Output is correct
2 Correct 0 ms 13652 KB Output is correct
3 Correct 43 ms 13784 KB Output is correct
4 Correct 33 ms 13784 KB Output is correct
5 Correct 36 ms 13784 KB Output is correct
6 Correct 39 ms 20728 KB Output is correct
7 Correct 36 ms 13784 KB Output is correct
8 Correct 33 ms 13852 KB Output is correct
9 Memory limit exceeded 29 ms 65536 KB Memory limit exceeded
10 Halted 0 ms 0 KB -