QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#824910 | #9770. Middle Point | ucup-team5318# | WA | 1ms | 4064kb | C++14 | 2.0kb | 2024-12-21 16:27:26 | 2024-12-21 16:27:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,m,ax,ay;
int lowbit(int x){return (x&-x);}
int cnt,ans[N][4];
void slv(int x,int y)
{
//cout<<x<<" "<<y<<endl;
if(x==0 || x==n)
{
if(y==0 || y==m)return ;
if(lowbit(y)<=lowbit(m))
{
int l=0,r=m;
while(l<=r)
{
int mid=l+r>>1;
cnt++,ans[cnt][0]=x,ans[cnt][1]=l,ans[cnt][2]=x,ans[cnt][3]=r;
if(mid==y)break;
else if(mid<y)l=mid;
else r=mid;
}
return ;
}
else printf("-1\n"),exit(0);
}
else if(y==0 || y==m)
{
if(x==0 || x==n)return ;
if(lowbit(x)<=lowbit(n))
{
int l=0,r=n;
while(l<=r)
{
int mid=l+r>>1;
cnt++,ans[cnt][0]=l,ans[cnt][1]=y,ans[cnt][2]=r,ans[cnt][3]=y;
if(mid==x)break;
else if(mid<x)l=mid;
else r=mid;
}
return ;
}
else printf("-1\n"),exit(0);
}
if(x*2<=n && y*2<=m)
{
slv(x*2,y*2);
cnt++,ans[cnt][0]=0,ans[cnt][1]=0,ans[cnt][2]=x*2,ans[cnt][3]=y*2;
}
else if(x*2<=n && m-2*(m-y)>=0)
{
slv(x*2,m-2*(m-y));
cnt++,ans[cnt][0]=0,ans[cnt][1]=m,ans[cnt][2]=x*2,ans[cnt][3]=m-2*(m-y);
}
else if(n-2*(n-x)>=0 && y*2<=m)
{
slv(n-2*(n-x),y*2);
cnt++,ans[cnt][0]=n,ans[cnt][1]=0,ans[cnt][2]=n-2*(n-x),ans[cnt][3]=y*2;
}
else
{
slv(n-2*(n-x),m-2*(m-y));
cnt++,ans[cnt][0]=n,ans[cnt][1]=m,ans[cnt][2]=n-2*(n-x),ans[cnt][3]=m-2*(m-y);
}
}
bool ck(int x,int l,int r)
{
if(x==l || x==r)return 0;
int mid=l+r>>1;
if(x==mid)return 0;
if((r-l)&1)return 1;
if(x<mid)return ck(x,l,mid);return ck(x,mid,r);
}
int main()
{
scanf("%d %d",&n,&m);
scanf("%d %d",&ax,&ay);
if(ck(ax,0,n) || ck(ay,0,m)){printf("-1\n");return 0;}
slv(ax,ay);
printf("%d\n",cnt);
map<pair<int,int>,int>mp;
mp[{0,0}]=mp[{0,m}]=mp[{n,0}]=mp[{n,m}]=1;
for(int i=1;i<=cnt;i++)
{
assert(mp.count({ans[i][0],ans[i][1]}));
assert(mp.count({ans[i][2],ans[i][3]}));
mp[{ans[i][0]+ans[i][2]>>1,ans[i][1]+ans[i][3]>>1}]=1;
}
for(int i=1;i<=cnt;i++)printf("%d %d %d %d\n",ans[i][0],ans[i][1],ans[i][2],ans[i][3]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4060kb
input:
2 2 1 1
output:
1 0 0 2 2
result:
ok correct!
Test #2:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
8 8 5 0
output:
3 0 0 8 0 4 0 8 0 4 0 6 0
result:
ok correct!
Test #3:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
0 0 0 0
output:
0
result:
ok correct!
Test #4:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
2024 0 1012 0
output:
1 0 0 2024 0
result:
ok correct!
Test #5:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
2024 2024 2023 2023
output:
-1
result:
ok correct!
Test #6:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
8 6 7 3
output:
3 0 6 8 6 4 6 8 6 8 0 6 6
result:
ok correct!
Test #7:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
2024 2026 2024 2026
output:
0
result:
ok correct!
Test #8:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
1000000000 1000000000 70 0
output:
-1
result:
ok correct!
Test #9:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
3 6 2 4
output:
-1
result:
ok correct!
Test #10:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
7 7 7 2
output:
-1
result:
ok correct!
Test #11:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
6 2 5 2
output:
-1
result:
ok correct!
Test #12:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
5 7 5 5
output:
-1
result:
ok correct!
Test #13:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
4 7 2 3
output:
-1
result:
ok correct!
Test #14:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
8 2 2 2
output:
2 0 2 8 2 0 2 4 2
result:
ok correct!
Test #15:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
3 3 0 2
output:
-1
result:
ok correct!
Test #16:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
7 7 1 4
output:
-1
result:
ok correct!
Test #17:
score: -100
Wrong Answer
time: 0ms
memory: 4064kb
input:
6 3 6 1
output:
1 6 0 6 3
result:
wrong answer non-lattice point is added into S.