QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#634106#9462. Safest Buildingsucup-team3564#AC ✓9ms24412kbC++143.0kb2024-10-12 16:43:012024-10-12 16:43:01

Judging History

你现在查看的是最新测评结果

  • [2024-10-12 16:43:01]
  • 评测
  • 测评结果:AC
  • 用时:9ms
  • 内存:24412kb
  • [2024-10-12 16:43:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long T,a,b,c,d[1000001],v[1000001],o,h[1000001],fa[1000001],q,w,e,an,cn,fac[1000001],inv[1000001],st[1000001],u[1000001];
char s[1000001];
struct p{long long q,w;}l[1000001];
long long pow_(long long qq,long long ww){long long ee=1;while(ww){if(ww&1) ee*=qq,ee%=mod;qq*=qq,qq%=mod,ww>>=1;}return ee%mod;}
inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*f;}
void add(long long qq,long long ww){l[++o].q=ww,l[o].w=h[qq],h[qq]=o;}
long long gcd(long long qq,long long ww){return !ww?qq:gcd(ww,qq%ww);}
long long find(long long qq){return qq==fa[qq]?qq:fa[qq]=find(fa[qq]);}
void merge(long long qq,long long ww){long long f1=find(qq),f2=find(ww);if(f1==f2) return;fa[f1]=f2;}
long long C(long long qq,long long ww){return fac[qq]*inv[ww]%mod*inv[qq-ww]%mod;}
map<vector<int>,long long> vi,ve;
int dfs(long long qq,long long ww,long long ee)
{
	vector<int> tmp;
	for(int i=1;i<=ee;i++) tmp.push_back(h[i]);
	if(vi[tmp])
	{
		return ve[tmp];
	}vi[tmp]=1;
	for(int i=1;i<=ee-2;i++)
	{
		if(h[i]==h[i+1]&&h[i+1]==h[i+2])
		{
			cn=0;
			for(int j=1;j<i;j++) st[++cn]=h[j];
			for(int j=i+3;j<=ee;j++) st[++cn]=h[j];
			for(int j=1;j<=cn;j++) h[j]=st[j];
			long long yy=dfs(qq+1,ww,ee-3);
			ve[tmp]=max(ve[tmp],yy+1);
			for(int j=0;j<tmp.size();j++) h[j+1]=tmp[j];
		}
	}
	for(int i=1;i<=ee-1;i++)
	{
		if(h[i]==h[i+1])
		{
			cn=0;
			for(int j=1;j<i;j++) st[++cn]=h[j];
			for(int j=i+2;j<=ee;j++) st[++cn]=h[j];
			for(int j=1;j<=cn;j++) h[j]=st[j];
			long long yy=dfs(qq+1,ww,ee-2);
			ve[tmp]=max(ve[tmp],yy);
			for(int j=0;j<tmp.size();j++) h[j+1]=tmp[j];
		}
	}
	for(int i=1;i<=ee;i++)
	{
		cn=0;
		for(int j=1;j<i;j++) st[++cn]=h[j];
		for(int j=i+1;j<=ee;j++) st[++cn]=h[j];
		for(int j=1;j<=cn;j++) h[j]=st[j];
		long long yy=dfs(qq+1,ww,ee-1);
		ve[tmp]=max(ve[tmp],yy);
		for(int j=0;j<tmp.size();j++) h[j+1]=tmp[j];
	}
	return ve[tmp];
}
mt19937 rnd(time(0));
int main()
{
//	freopen("1.in","r",stdin);
	srand((unsigned)(time(0)^(*new int)));
	fac[0]=1;for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
	inv[1000000]=pow_(fac[1000000],mod-2);for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	T=1;
	scanf("%lld",&T);
	for(int ii=1;ii<=T;ii++)
	{
		scanf("%lld%lld%lld",&a,&b,&c);
		cn=0;
		long long mn=1e12;
		long long yy=max(b-c*2,(long long)(0));
		for(int i=1;i<=a;i++)
		{
			scanf("%lld%lld",&q,&w);
			if(b-c*2>=0)
			{
				long long gg=q*q+w*w;
				gg=max(gg,yy*yy);
				if(gg<mn) mn=gg,cn=0,st[++cn]=i;
				else if(gg==mn) st[++cn]=i;
			}
			else
			{
				long long gg=q*q+w*w;
				long long tt=c*2-b;
				gg=max(gg,tt*tt);
				if(gg<mn) mn=gg,cn=0,st[++cn]=i;
				else if(gg==mn) st[++cn]=i;
			}
		}
		printf("%lld\n",cn);
		for(int i=1;i<=cn;i++)
		{
			printf("%lld",st[i]);
			if(i!=cn)printf(" ");
		}
		printf("\n");
	}
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 24412kb

input:

2
3 10 5
3 4
3 5
3 6
3 10 4
-7 -6
4 5
5 4

output:

1
1
2
2 3

result:

ok 5 tokens

Test #2:

score: 0
Accepted
time: 9ms
memory: 24388kb

input:

100
6 100 50
42 -31
-66 7
13 84
94 13
51 -14
-18 9
12 100 50
-78 56
-56 -64
-22 54
-41 14
-14 55
21 -83
75 21
-51 56
-31 74
-34 79
22 -37
1 -12
14 100 50
15 71
-44 41
-56 78
-48 22
42 -2
-70 28
51 -34
49 -31
-36 67
63 70
34 9
27 -33
36 -93
-52 -19
8 100 14
21 89
67 60
-12 -3
24 -37
-51 14
-30 8
-75 ...

output:

1
6
1
12
1
11
4
3 4 5 6
7
1 4 6 8 9 12 13
1
1
6
2 4 5 7 13 14
7
1 3 4 5 6 7 9
1
11
9
1 2 3 4 5 6 7 8 9
1
29
1
5
1
29
47
1 2 3 4 5 6 7 9 10 11 12 14 17 18 19 21 22 24 25 26 27 28 30 31 32 33 34 35 36 37 38 39 40 41 43 44 45 46 47 48 50 51 52 53 54 55 56
2
21 29
20
1 5 6 7 10 13 14 18 21 25 26 30 33 3...

result:

ok 1674 tokens

Extra Test:

score: 0
Extra Test Passed