QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#634106 | #9462. Safest Buildings | ucup-team3564# | AC ✓ | 9ms | 24412kb | C++14 | 3.0kb | 2024-10-12 16:43:01 | 2024-10-12 16:43:01 |
Judging History
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