申请修改题面、修改数据格式、添加 hack 数据
查看原帖
申请修改题面、修改数据格式、添加 hack 数据
195942
Terrible楼主2024/3/24 16:31

修改题面

题目描述 12and6=412 \text{and} 6=4 中的 and\mathrm{and} 两边没有空出来,改为 12 and 6=412\ \text{and}\ 6=4($12\ \text{and}\ 6=4$)。

题目没有给出不存在契合度的应对描述,所以要求存在契合度,必然有 N≥2N\geq 2。

数据范围中的 n≤106n\leq 10^6,建议修改为 2≤N≤1062\leq N\leq 10^6($2\leq N\leq 10^6$) 或 N≤106N\leq 10^6($N\leq 10^6$)。

修改数据格式

本题数据存在严重的格式错误,通过提交 Python 代码

try:
    n=int(input())
except:
    exit(2)
cnt=0
try:
    while 1:
        input()
        cnt+=1
except:
    pass
if cnt!=1:
    if n==cnt:exit(3)
else:
    exit(4)

记录 中发现,结果全是 exit(3),说明数据共有 n+1n+1 行。通过 Python AC 记录 还可以得出每行上都有一个数字(这与题面相悖)。

添加 hack 数据

由于题面中写到 N≤106N\leq 10^6,如果这不是在唬人的话,应该有一个数据的 NN 和 10610^6 也大差不差才算实至名归吧?之前的讨论区里已经有一堆请求加强数据的帖子了。

下面提供若干个大数据 & hack 数据的生成器。

建议将新加入的测试点加入一个 0 分的 subtask 里面,另外题面似乎还提及到了使用 Python 的事情,如果想让绝大部分同学写的 Python 还能通过本题的话,建议把这个 subtask 的时限开到 2.00s(可能依然会卡一小部分代码,但是应该基本都能过)。

#include<set>
#include<cstdio>
#include<vector>
#include<cassert>
#include<random>
#include<algorithm>
struct _once
{bool f=1;void set(){f=1;}bool operator()(){bool res=f;f=0;return res;}}once;
#define seed 0xabcabc84
#define para std::vector<int> a
class Solution
{
public:
	int operator()(para)
	{
		std::vector<int> temp;
		for(int i=30;i>=0;i--)
		{
			for(auto j:a)if(j&1<<i)temp.push_back(j);
			if(temp.size()>=2)std::swap(a,temp);
			temp.clear();
		}
		return a[0]&a[1];
	}
};
void outer(para)
{
	int N=a.size();
	assert(2<=N&&N<=1000000);
	for(auto i:a)assert(0<=i&&i<=2147483647);
	//===========================checker=========================================
	static int outer_order=0;
	std::string index=std::to_string(++outer_order);
	FILE*in=freopen(("add"+index+".in").c_str(),"wb",stdout);
	//============================std.in=========================================
	printf("%d\n",N);once.set();
	for(auto i:a)
	{
		if(!once())putchar(' ');
		printf("%d",i);
	}
	//============================std.in=========================================
	fclose(in);
	FILE*out=freopen(("add"+index+".out").c_str(),"wb",stdout);
	//============================std.out========================================
	Solution solution;
	printf("%d",solution(a));
	//============================std.out========================================
	fclose(out);
}
std::mt19937_64 rnd(seed);
std::vector<int> uniform_random_vector(const int n)
{
	std::vector<int> res(n);
	std::uniform_int_distribution<int> U(0,2147483647);
	for(int i=0;i<n;i++)res[i]=U(rnd);
	return res;
}
std::vector<int> m_kinds_of_numbers_vector(const int n,const int m)
{//只有若干个不同的数字,m 是不同的数字个数
	std::vector<int> res(n),num(m);
	std::uniform_int_distribution<int> U(0,2147483647),lectU(0,m-1);
	std::set<int> s;
	for(int i=0;i<m;i++)
	{
		do num[i]=U(rnd);while(s.find(num[i])!=s.end());
		s.insert(num[i]);
	}
	for(int i=0;i<n;i++)res[i]=num[lectU(rnd)];
	return res;
}
std::vector<int> no_same_number_vector(const int n)
{
	std::vector<int> res(n);
	std::uniform_int_distribution<int> U(0,2147483647);
	std::set<int> s;
	for(int i=0;i<n;i++)
	{
		do res[i]=U(rnd);while(s.find(res[i])!=s.end());
		s.insert(res[i]);
	}
	assert(s.size()==n);
	return res;
}
std::vector<int> kth_power_vector(const int n,int HighestBitPos=30)
{
	//2^k 的数每种有一个,1 有两个,其他都是 0
	assert(n>=HighestBitPos+2);
	std::vector<int> res(n);
	for(int i=0;i<=HighestBitPos;i++)res[i]=1<<i;
	res[HighestBitPos+1]=1;
	std::shuffle(res.begin(),res.end(),rnd);
	return res;
}
std::vector<int> higher_single_lower_random_vector(const int n)
{
	assert(n>=40);
	const int stdpos=15,midbit=1<<stdpos;
	std::vector<int> res(n);
	std::uniform_int_distribution<int> U(0,(1<<stdpos)-1);
	for(int i=stdpos+1;i<=30;i++)res[i-stdpos-1]|=1<<i;
	res[19-stdpos-1]|=midbit,res[28-stdpos-1]|=midbit;
	for(auto&i:res)i|=U(rnd);
	std::shuffle(res.begin(),res.end(),rnd);
	return res;
}
int main()
{
	outer(uniform_random_vector(1e6));//随机大数据
	outer(m_kinds_of_numbers_vector(1e5,40));//40 种数的大数据,目前不知道会卡掉谁
	outer(no_same_number_vector(1e6));//各个不同数的大数据
	outer(kth_power_vector(40));//如果枚举不到前32大的数就寄了
	outer(higher_single_lower_random_vector(1e6));//卡只查大小相近的两个数
	outer({4,5});//小数据点
	return 0;
}
2024/3/24 16:31
加载中...