QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#825863 | #9770. Middle Point | ucup-team3474# | RE | 0ms | 3576kb | C++23 | 2.4kb | 2024-12-21 23:50:20 | 2024-12-21 23:50:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll a,b,x,y;
void cal(vector<PII> &v,ll len,ll x){
// cout<<len<<" "<<x<<endl;
if(x==0) return;
ll lb=0;
ll cnt=0;
while((1ll<<cnt)<len) cnt++;
while(((1ll<<lb)&x)==0) lb++;
ll l=0,r=len;
while(cnt>lb){
ll mid=l+r>>1;
v.push_back({l,r});
if((x>>(cnt-1))&1) l=mid;
else r=mid;
cnt--;
}
}
bool check(vector<array<ll,4>> ans,ll ansx,ll ansy,ll a,ll b){
set<PII> se;
// cout<<a<<" "<<b<<endl;
se.insert({0,0});
se.insert({a,0});
se.insert({0,b});
se.insert({a,b});
for(auto num:ans){
int x=num[0],y=num[1],u=num[2],v=num[3];
if((x+u)%2||(y+v)%2) return false;
if(!se.count({x,y})||!se.count({u,v})) return false;
se.insert({(x+u)/2,(y+v)/2});
}
return se.count({ansx,ansy});
}
void __(){
cin>>a>>b>>x>>y;
ll ra=a,rb=b;
ll ansx=x,ansy=y;
ll basea=a,baseb=b;
ll lena=1,lenb=1;
while(basea!=0&&basea%2==0){
basea/=2;
lena<<=1;
}
while(baseb!=0&&baseb%2==0){
baseb/=2;
lenb<<=1;
}
if(basea!=0&&x%basea!=0){
puts("-1");
return;
}
if(basea!=0)
x/=basea;
if(baseb!=0&&y%baseb!=0){
puts("-1");
return;
}
if(baseb!=0)
y/=baseb;
vector<PII> vx,vy;
cal(vx,lena,x);
cal(vy,lenb,y);
int cha=vx.size()-vy.size();
cha=abs(cha);
if(vx.size()<vy.size()){
vector<PII> vxx=vx;
vx.clear();
while(cha--) vx.push_back({0,0});
for(auto x:vxx) vx.push_back(x);
}else{
vector<PII> vyy=vy;
vy.clear();
while(cha--) vy.push_back({0,0});
for(auto x:vyy) vy.push_back(x);
}
// while(vx.size()<vy.size()) vx.push_back({x,x});
// while(vy.size()<vx.size()) vy.push_back({y,y});
vector<array<ll,4>> answww;
cout<<vx.size()<<endl;
for(int i=0;i<vx.size();i++){
cout<<vx[i].first*basea<<" "<<vy[i].first*baseb<<" "<<vx[i].second*basea<<" "<<vy[i].second*baseb<<"\n";
answww.push_back({vx[i].first*basea,vy[i].first*baseb,vx[i].second*basea,vy[i].second*baseb});
}
if(!check(answww,ansx,ansy,ra,rb)) assert(0);
}
int main(){
int _=1;
// cin>>_;
while(_--){
__();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3524kb
input:
2 2 1 1
output:
1 0 0 2 2
result:
ok correct!
Test #2:
score: 0
Accepted
time: 0ms
memory: 3504kb
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: 3576kb
input:
0 0 0 0
output:
0
result:
ok correct!
Test #4:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
2024 0 1012 0
output:
1 0 0 2024 0
result:
ok correct!
Test #5:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
2024 2024 2023 2023
output:
-1
result:
ok correct!
Test #6:
score: 0
Accepted
time: 0ms
memory: 3432kb
input:
8 6 7 3
output:
3 0 0 8 0 4 0 8 0 6 0 8 6
result:
ok correct!
Test #7:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
2024 2026 2024 2026
output:
0
result:
ok correct!
Test #8:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
1000000000 1000000000 70 0
output:
-1
result:
ok correct!
Test #9:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
3 6 2 4
output:
-1
result:
ok correct!
Test #10:
score: 0
Accepted
time: 0ms
memory: 3452kb
input:
7 7 7 2
output:
-1
result:
ok correct!
Test #11:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
6 2 5 2
output:
-1
result:
ok correct!
Test #12:
score: 0
Accepted
time: 0ms
memory: 3448kb
input:
5 7 5 5
output:
-1
result:
ok correct!
Test #13:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
4 7 2 3
output:
-1
result:
ok correct!
Test #14:
score: -100
Runtime Error
input:
8 2 2 2
output:
2