Submission #28796

#	Time	Username	Problem	Language	Result	Execution time	Memory
28796		kajebiii	Oriental P.A.D.A.K (FXCUP2_padak)	C++14	1 / 1	513 ms	13740 KiB

padak

#include <stdio.h>
#include <bits/stdc++.h>
 
using namespace std;
 
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi; typedef pair<ll, int> pli; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;
 
const int MAX_V = 1e6 + 100;
 
int N, M, K, B, Z;
int When[MAX_V], Q[MAX_V], List[MAX_V]; int r=0, f=0, ln = 0;
inline pi toPi(int s) {return pi(s/M, s%M);}
inline int toS(int x, int y) {return x*M+y;}
int main() {
	cin >> N >> M >> K >> B >> Z;
	for(int i=0; i<N; i++) for(int j=0; j<M; j++) When[toS(i, j)] = -1;
	for(int k=0; k<K; k++) {
		int x, y; scanf("%d%d", &x, &y); x--; y--;
		When[toS(x, y)] = 0;
		Q[r++] = toS(x, y);
	}
	int maxK = -1;
	while(f < r) {
		int s = Q[f]; f++;
		int x, y; tie(x, y) = toPi(s);
		int v = When[s];
//		printf("%d %d : %d\n", x, y, v);
		List[ln++] = maxK = v;
		for(int k=0; k<4; k++) {
			int nx = x + "1012"[k] - '1', ny = y + "0121"[k] - '1';
			if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
			if(When[toS(nx,ny)] != -1) continue;
			When[toS(nx, ny)] = v+1;
//			printf("push %d %d [%d]\n", nx, ny, v+1);
			Q[r++] = toS(nx, ny);
		}
	}
	int ix = 0, maxAns = 0;
	for(int k=1; k<=maxK+1; k++) {
		while(ix < ln && List[ix] < k) ix++;
		int now = min(Z, ln - ix);
		maxAns += now;
		ix += now;
	}
	int minAns = 0;
	ix = ln - 1;
	for(int k=1; k<=maxK+1; k++) {
		for(int i=0; i<Z; i++) {
			if(ix < 0 || List[ix] < k) break;
			minAns++; ix--;
		}
		if(ix < 0 || List[ix] < k) break;
	}
	printf("%d %d\n", minAns, maxAns);
 
	return 0;
}

Compilation message (stderr)

padak.cpp: In function 'int main()':
padak.cpp:26:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y); x--; y--;
                                  ^

• Subtask 1: 1 / 1