QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#852055#9770. Middle PointWanyeWA 1ms4884kbC++142.2kb2025-01-11 09:54:272025-01-11 09:54:28

Judging History

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

  • [2025-01-11 09:54:28]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4884kb
  • [2025-01-11 09:54:27]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define N 50005
using namespace std;
vector<ll> op[N];
struct node{ll a,b,c,d;};
ll a,b,x,y,ta,tb,la,ra,lb,rb,viss[N];
vector<node> ans,temp,ans2;
map<pair<ll,ll>,bool> vis;
inline void dfs(ll x){
	viss[x] = 1;
	for(ll i=0;i<op[x].size();i++){
		if(!viss[op[x][i]]) dfs(op[x][i]);
	}
}
int main(){
	cin>>a>>b>>x>>y;
	if(x==0&&y==0||x==a&&y==0||x==0&&y==b||x==a&&y==b){
		cout<<0<<endl;
		return 0;
	}
	if(a){
		ta = a;
		while(ta%2==0) ta/=2;
		if(x%ta!=0){
			cout<<-1<<endl;
			return 0;
		}
	}
	if(b){
		tb = b;
		while(tb%2==0) tb/=2;
		if(y%tb!=0){
			cout<<-1<<endl;
			return 0;
		}
	}
	la=0,ra=a,lb=0,rb=b;
	while(1){
		if(la==x&&lb==y) break;
		if(la==x&&rb==y) break;
		if(ra==x&&lb==y) break;
		if(ra==x&&rb==y) break;
		ll mida = (la+ra)/2,midb = (lb+rb)/2;
		ans.push_back((node){la,lb,ra,rb});
		if(x<=mida&&y<=midb){
			ans.push_back((node){la,lb,ra,lb});
			ans.push_back((node){la,lb,la,rb});
			ra = mida,rb = midb;
		}
		else if(x>=mida&&y>=midb){
			ans.push_back((node){la,rb,ra,rb});
			ans.push_back((node){ra,lb,ra,rb});
			la = mida,lb = midb;
		}
		else if(x<=mida&&y>=midb){
			ans.push_back((node){la,rb,ra,rb});
			ans.push_back((node){la,lb,la,rb});			
			ra = mida,lb = midb;
		}
		else{
			ans.push_back((node){ra,lb,ra,rb});
			ans.push_back((node){la,lb,ra,lb});			
			la = mida,rb = midb;
		}
	}
	vis[make_pair(0,0)]=vis[make_pair(0,b)]=vis[make_pair(a,0)]=vis[make_pair(a,b)]=1;
	for(int i=0;i<ans.size();i++){
		int tx = (ans[i].a+ans[i].c)/2,ty = (ans[i].b+ans[i].d)/2;
		if(vis[make_pair(tx,ty)]) continue;
		else vis[make_pair(tx,ty)]=1,temp.push_back(ans[i]);
	}
	int pos = -1;
	for(int i=0;i<temp.size();i++){
		int tx = (temp[i].a+temp[i].c)/2,ty = (temp[i].b+temp[i].d)/2;
		if(tx==x&&ty==y) pos=i;
		for(int j=i+1;j<temp.size();j++){
			if(temp[j].a==tx&&temp[j].b==ty||temp[j].c==tx&&temp[j].d==ty) op[j].push_back(i);
		}
	}
	dfs(pos);
	for(int i=0;i<temp.size();i++) if(viss[i]) ans2.push_back(temp[i]);
	cout<<ans2.size()<<endl;
	for(int i=0;i<ans2.size();i++) cout<<ans2[i].a<<" "<<ans2[i].b<<" "<<ans2[i].c<<" "<<ans2[i].d<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4844kb

input:

2 2
1 1

output:

1
0 0 2 2

result:

ok correct!

Test #2:

score: 0
Accepted
time: 1ms
memory: 4844kb

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: 1ms
memory: 4884kb

input:

0 0
0 0

output:

0

result:

ok correct!

Test #4:

score: 0
Accepted
time: 1ms
memory: 4812kb

input:

2024 0
1012 0

output:

1
0 0 2024 0

result:

ok correct!

Test #5:

score: 0
Accepted
time: 0ms
memory: 4856kb

input:

2024 2024
2023 2023

output:

-1

result:

ok correct!

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 4884kb

input:

8 6
7 3

output:

5
0 0 8 6
8 0 8 6
8 3 8 6
4 3 8 3
6 3 8 4

result:

wrong answer non-lattice point is added into S.