hack 数据

hack 输入

1 1 1 6
1000000000
1 1 1 1 1 1 1000000000
1 1 1 1 1 1 1000000000
1 1 1 1 1 1 1000000000
1 1 1 1 1 1 0
1 1 1 1 1 1 0
1 1 1 1 1 1 0

hack 答案

2

hack 输出 #1

6

hack 输出 #2

7

hack 原理

$m\le10^6,h_t\le 10^9$

在差分数组上某位置增加或减少的 $h_t$ 的总和可能溢出 int，例如上面的 hack 数据中，如果检查 $\ge3$ 次攻击，则会由于 $(1, 1, 1)$ 位置连续加了 $3$ 次 $10^9$ 溢出 int 变为负数，导致误判没有爆炸。

后面添加的攻击 1 1 1 1 1 1 0 是为了凑足 $m$，防止二分法直接判断 $2$ 次攻击，可以看出如果直接判断 $2$ 次攻击的话则能正确判断出爆炸。

由于判断 $3$ 次攻击时认为没有爆炸，因此正确答案 $2$ 被排除到二分范围外，被 hack 程序检查后面的攻击时发现始终没有爆炸，因此输出 $6$ 或 $7$，这取决于程序是否利用 保证一定存在这样的战舰。 来调整二分法。

被 hack 的题解

截止发帖，共有 $14$ 篇题解，其中有完整代码的共计 $11$ 篇，其中 $8$ 篇题解代码不能通过 hack，$2$ 篇能通过 hack 的代码不能 AC，仅有 $1$ 篇题解代码能通过 hack 且 AC，甚至还是用的 #define int long long 才过的。

题解 #1

6

题解 #2

6

题解 #3

6

题解 #4

7

题解 #5

6

题解 #6

7

题解 #7

该题解代码虽然能通过 hack，但是不能通过本题已有的任何一个测试点。
评测记录，可以看到不仅 WA，而且严重超时。

题解 #8

6

题解 #9

该题解代码虽然能通过 hack，但是不能通过本题的测试点 #5 #6。
评测记录，可以看到测试点 #5 #6 WA。

题解 #10

7

对照代码

能通过 hack 的代码

评测记录

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int64;

int A, B, C, m;

vector<vector<vector<int> > > d;
vector<vector<vector<int64> > > damage;

int la[1000000], ra[1000000], lb[1000000], rb[1000000], lc[1000000], rc[1000000], h[1000000];

bool check(int attack){
	for(int i=0; i<A; ++i){
		for(int j=0; j<B; ++j){
			vector<int64>& subdamage = damage[i][j];
			for(int k=0; k<C; ++k){
				subdamage[k] = 0;
			}
		}
	}
	for(int i=0; i<attack; ++i){
		damage[la[i]][lb[i]][lc[i]] += h[i];
		damage[la[i]][lb[i]][rc[i]+1] -= h[i];
		damage[la[i]][rb[i]+1][lc[i]] -= h[i];
		damage[la[i]][rb[i]+1][rc[i]+1] += h[i];
		damage[ra[i]+1][lb[i]][lc[i]] -= h[i];
		damage[ra[i]+1][lb[i]][rc[i]+1] += h[i];
		damage[ra[i]+1][rb[i]+1][lc[i]] += h[i];
		damage[ra[i]+1][rb[i]+1][rc[i]+1] -= h[i];
	}
	
	for(int i=0; i<A; ++i){
		for(int j=0; j<B; ++j){
			for(int k=0; k<C; ++k){
				damage[i][j][k+1] += damage[i][j][k];
			}
		}
	}
	for(int i=0; i<A; ++i){
		for(int j=0; j<B; ++j){
			for(int k=0; k<C; ++k){
				damage[i][j+1][k] += damage[i][j][k];
			}
		}
	}
	for(int i=0; i<A; ++i){
		for(int j=0; j<B; ++j){
			for(int k=0; k<C; ++k){
				damage[i+1][j][k] += damage[i][j][k];
			}
		}
	}
	for(int i=0; i<A; ++i){
		for(int j=0; j<B; ++j){
			vector<int>& subd = d[i][j];
			vector<int64>& subdamage = damage[i][j];
			for(int k=0; k<C; ++k){
				if(subdamage[k]>subd[k]) return false;
			}
		}
	}
	return true;
}

int main(){
	scanf("%d%d%d%d",&A,&B,&C,&m);
	d.resize(A);
	for(int i=0; i<A; ++i){
		d[i].resize(B);
		for(int j=0; j<B; ++j){
			d[i][j].resize(C);
			vector<int>& subd = d[i][j];
			for(int k=0; k<C; ++k){
				scanf("%d", &subd[k]);
			}
		}
	}
	damage.resize(A+1);
	for(int i=0; i<=A; ++i){
		damage[i].resize(B+1);
		for(int j=0; j<=B; ++j){
			damage[i][j].resize(C+1);
		}
	}
	for(int i=0; i<m; ++i){
		scanf("%d%d%d%d%d%d%d",la+i,ra+i,lb+i,rb+i,lc+i,rc+i,h+i);
		--la[i];
		--ra[i];
		--lb[i];
		--rb[i];
		--lc[i];
		--rc[i];
	}
	int ans = lower_bound((char*)1, (char*)m, 0, [](char& attack, int _){
		bool res = check(&attack-(char*)0);
		return res;
	})-(char*)0;
	printf("%d", ans);
}

不能通过 hack 的代码

评测记录

将上面的代码的第 $5$ 行 typedef long long int64; 改为 typedef int int64;，即将本应该使用 $64$ 位整数的地方改为使用 $32$ 位整数。

输出：

6