Submission #28612

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
28612	2017-07-16T07:59:23 Z	볼빨간 승관이(#1152, sys7961, deneb2016, hyorothy)	Oriental P.A.D.A.K (FXCUP2_padak)	C++11	0 / 1	49 ms	65536 KB

padak

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <set>
#include <unordered_map>
#include <list>
#include <unordered_set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#define INFI 987654321
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
struct Node{
    int x, y, dist;
};
int N, M, K, B, Z;
vector<vector<bool>> visit;
vector<int> data;
int dx[] = {1, 0, 0, -1};
int dy[] = {0, 1, -1, 0};
int main() {
    ios_base::sync_with_stdio(false);
    cin >> N >> M >> K >> B >> Z;
    assert((ll)N*M<=1000000);
    visit.resize(N + 1);
    for(int i = 1; i <= N; ++i)
        visit[i].resize(M + 1, 0);
    queue<Node> que;
    for(int i = 0; i < K; ++i) {
        Node here;
        cin >> here.x >> here.y;
        here.dist = 0;
        visit[here.x][here.y] = true;
        que.push(here);
    }
    while(que.empty() == false) {
        Node here = que.front();
        //cout << here.x << " " << here.y << endl;
        que.pop();
        data.push_back(here.dist);
        for(int i = 0; i < 4; ++i) {
            Node there = here;
            there.x += dx[i];
            there.y += dy[i];
            there.dist++;
            if(there.x < 1 || there.y < 1 || there.x > N || there.y > M)
                continue;
            if(visit[there.x][there.y] == 0) {
                que.push(there);
                visit[there.x][there.y] = true;
            }
        }
    }
    reverse(data.begin(), data.end());
    vector<int> data2;
    int mini = 0, maxi = 0, t = 0, cur = 0;

    while(data.empty() == false) {
        while(data.empty() == false && data.back() <= t) {
            data2.push_back(data.back());
            data.pop_back();
        }

        for(int i = 0; i < Z; ++i) {
            if(data.empty())
                break;
            data2.push_back(data.back());
            data.pop_back();
            maxi++;
        }
        t++;
    }

    reverse(data2.begin(), data2.end());
    t = 0;
    while(data2.empty() == false) {
        while(data2.empty() == false && data2.back() <= t)
            data2.pop_back();

        for(int i = 0; i < Z; ++i) {
            if(cur >= data2.size())
                break;
            mini++;
            cur++;
        }
        t++;
    }
    cout << mini << " " << maxi;
    return 0;
}

Compilation message

padak.cpp: In function 'int main()':
padak.cpp:88:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(cur >= data2.size())
                    ^

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2184 KB	Output is correct
2	Correct	0 ms	2184 KB	Output is correct
3	Correct	43 ms	14696 KB	Output is correct
4	Correct	39 ms	14684 KB	Output is correct
5	Correct	43 ms	14648 KB	Output is correct
6	Correct	43 ms	21548 KB	Output is correct
7	Correct	43 ms	14636 KB	Output is correct
8	Correct	46 ms	14636 KB	Output is correct
9	Memory limit exceeded	49 ms	65536 KB	Memory limit exceeded
10	Halted	0 ms	0 KB	-