luogu loj 70 官方10分,已经申诉,等待结果
查看原帖
luogu loj 70 官方10分,已经申诉,等待结果
80243
吴耀坤楼主2021/12/4 22:33

本地测70%的数据,开o2,ccf 是开o2的 i5 7267 550ms g++8 c++14 i7 7200u 504ms g++9 c++14

希望官方能给个合理的申诉结果 luogu 7个点,每个580ms,距离时间1s还差很久

#include<bits/stdc++.h>
#define pb_(x) push_back((x));
using namespace std;
const int N = 1e7 + 100;
bool b[N + 100];
int n;
int T;
vector<pair<int,int> > t;
set<int> s;
bool judge(int x)
{
	if(x % 7 == 0)
		return 1;
	while(x)
	{
		if(x % 10 == 7)
			return 1;
		x/=10;
	}
	return 0;
}
int find(int x)
{
	int l = 0, r = t.size() - 1,mid,ans = -1;
	if(b[x] == 0)
		return x;
	while(l <= r)
	{
		mid = l + r >> 1;
		if(t[mid].first >= x)	
			r = mid - 1, ans  = mid;
		else
			l = mid + 1;
	}
	return t[ans].second;
}
int main()
{
	//freopen("number.in","r",stdin);
//	freopen("number.out","w",stdout);
	scanf("%d", &T);
	for (long long i = 400000; i >= 1 ; i--)
	{
		if(judge(i))
			s.insert(i),b[i] = 1;
	}
	for (long long i = 400000; i >= 1 ; i--)
	{
		if(b[i])
			s.insert(i);
		for (set<int>::iterator it = s.begin();it != s.end() && (long long)*it * i <= N; it++)
			b[i * (*it)] = 1;	
	}
	int q = 0,p = 0;
	for (int i = 1; i <= 400000; i++)
	{
		if(!b[i])
			p = i;
		else 
		{
			t.pb_(make_pair(p,q));
			q = i + 1;
		}
	}
	while(T--)
	{
		int x;
		scanf("%d",&x);
		if(b[x])
			puts("-1");
		else
		{
			int p = find(x + 1);
			printf("%d\n",p);
		}
	}
}

2021/12/4 22:33
加载中...