QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#784472 | #692. Delete the Points | hysbzdkf | WA | 2ms | 3708kb | C++14 | 3.2kb | 2024-11-26 15:06:53 | 2024-11-26 15:06:54 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n;
struct node{
int x,y;
}a[3001];
node q1[11];
bool flag1[11],ans_flag;
void solve1(int dep){
// cout<<"__________"<<dep<<"_________"<<endl;
if(dep==n){
cout<<"Yes"<<endl;
for(int i=1;i<=n/2;i++){
cout<<q1[i*2-1].x<<" "<<q1[i*2-1].y<<" ";
cout<<q1[i*2].x<<" "<<q1[i*2].y<<endl;
}
ans_flag=1;
return ;
}
for(int i=1;i<=n;i++){
if(flag1[i])continue;
for(int j=i+1;j<=n;j++){
if(flag1[j])continue;
node s={min(a[i].x,a[j].x),min(a[i].y,a[j].y)};
node t={max(a[i].x,a[j].x),max(a[i].y,a[j].y)};
int line_x=t.x-s.x,line_y=t.y-s.y;
bool cp_flag=1;
for(int k=1;k<=n;k++){
if(flag1[k]||k==i||k==j)continue;
if(a[k].x>=s.x&&a[k].x<=t.x&&a[k].y>=s.y&&a[k].y<=t.y)cp_flag=0;
}
if(cp_flag){
// cout<<s.x<<" "<<s.y<<" "<<t.x<<" "<<t.y<<endl;
// cout<<114514<<endl;
if(line_x>line_y){
int left=0,right=1e18;
for(int k=1;k<=n;k++){
if(flag1[k]||k==i||k==j)continue;
if(a[k].x<s.x||a[k].x>t.x)continue;
if(a[k].y<t.y)left=max(left,a[k].y);
if(a[k].y>s.y)right=min(right,a[k].y);
}
// cout<<"test1:"<<endl;
// cout<<"l&r:"<<left<<" "<<right<<endl;
if(left==0||right==1e18||right-left-2>=line_x){
q1[dep+1].x=s.x;
if(left==0)q1[dep+1].y=t.y-line_x;
else q1[dep+1].y=max(left+1,t.y-line_x);
q1[dep+2].x=t.x;
q1[dep+2].y=q1[dep+1].y+line_x;
flag1[i]=1;
flag1[j]=1;
solve1(dep+2);
flag1[i]=0;
flag1[j]=0;
if(ans_flag)return ;
// cout<<"right"<<endl;
}
}
else{
int up=0,down=1e18;
for(int k=1;k<=n;k++){
if(flag1[k]||k==i||k==j)continue;
if(a[k].y<s.y||a[k].y>t.y)continue;
if(a[k].x<t.x)up=max(up,a[k].x);
if(a[k].x>s.x)down=min(up,a[k].x);
}
// cout<<"test2:"<<endl;
// cout<<"u&d:"<<up<<" "<<down<<endl;
if(up==0||down==1e18||down-up-2>=line_y){
q1[dep+1].y=s.y;
if(up==0)q1[dep+1].x=t.x-line_y;
else q1[dep+1].x=max(up+1,t.x-line_x);
q1[dep+2].y=t.y;
q1[dep+2].x=q1[dep+1].x+line_y;
flag1[i]=1;
flag1[j]=1;
solve1(dep+2);
flag1[i]=0;
flag1[j]=0;
if(ans_flag)return ;
// cout<<"right"<<endl;
}
}
}
}
}
}
void solve2(){
ans_flag=1;
cout<<"Yes"<<endl;
for(int i=1;i<=n/2;i++){
cout<<a[i*2-1].x<<" "<<a[i*2-1].y<<" ";
cout<<a[i*2].x<<" "<<a[i*2].y<<endl;
}
}
bool cmp(node x,node y){
return x.y<y.y;
}
void solve3(){
ans_flag=1;
sort(a+1,a+1+n,cmp);
cout<<"Yes"<<endl;
for(int i=1;i<=n/2;i++){
cout<<a[i*2-1].x<<" "<<a[i*2-1].y<<" ";
int dt=a[i*2].y-a[i*2-1].y;
cout<<dt<<" "<<a[i*2].y<<endl;
}
}
signed main(){
// freopen("stone.in","r",stdin);
// freopen("stone.out","w",stdout);
// cin>>T;
// while(T--){
cin>>n;
bool flag2=1,flag3=1;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
if(a[i].x!=2*i||a[i].y!=2*i)flag2=0;
if(a[i].x!=0)flag3=0;
}
if(n<=10)solve1(0);
else{
if(flag2)solve2();
else{
if(flag3)solve3();
}
}
if(!ans_flag)
cout<<"No"<<endl;
// }
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
input:
4 1 1 2 2 5 5 6 6
output:
Yes 1 1 2 2 5 5 6 6
result:
ok OK
Test #2:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
4 0 0 1 2 2 1 4 4
output:
Yes -1 0 1 2 1 1 4 4
result:
ok OK
Test #3:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
4 1 2 3 2 2 1 2 3
output:
Yes 1 1 2 2 2 2 3 3
result:
ok OK
Test #4:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
6 12 9 1 5 10 14 20 14 15 4 7 9
output:
Yes 12 6 20 14 1 -9 15 5 5 9 10 14
result:
ok OK
Test #5:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
10 39 72 59 52 23 17 2 31 30 0 25 88 2 36 61 23 4 96 59 76
output:
Yes 39 52 59 72 2 10 23 31 -6 0 30 36 4 75 25 96 8 23 61 76
result:
ok OK
Test #6:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
10 53 95 37 51 84 11 3 39 31 20 37 84 42 27 95 38 6 6 16 19
output:
Yes 37 79 53 95 3 21 37 55 31 -33 84 20 42 -15 95 38 3 6 16 19
result:
ok OK
Test #7:
score: -100
Wrong Answer
time: 2ms
memory: 3672kb
input:
3000 997371332 135791687 997371332 135791686 997371332 135791685 997371333 135791685 997371333 135791687 997371334 135791687 997371333 135791688 997371331 135791686 997371333 135791689 997371334 135791686 997371334 135791689 997371333 135791684 997371332 135791689 997371331 135791685 997371334 13579...
output:
No
result:
wrong answer The participant does not have a solution