QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#369154 | #2434. Single Cut of Failure | InfinityNS# | WA | 3305ms | 381148kb | C++20 | 4.2kb | 2024-03-27 21:08:10 | 2024-03-27 21:08:10 |
Judging History
answer
#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;
const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}
const int maxn=2e6+10;
struct pt{
ll x,y;
pt(){}
pt(ll x,ll y){
this->x=x;
this->y=y;
}
pt operator -(pt b){
return pt(x-b.x,y-b.y);
}
pt operator +(pt b){
return pt(x+b.x,y+b.y);
}
ll cross(pt b){
return x*b.y-y*b.x;
}
ll sqdist(){
return x*x+y*y;
}
void ispis(){
printf("%lld %lld PT\n",x,y);
}
};
using int128=__uint128_t;
typedef pair<pt,int128> ptl;
typedef pair<pt,pt> ptt;
bool cmp(ptl &a,ptl &b){
pt pta=a.ff;
pt ptb=b.ff;
ll pom=pta.cross(ptb);
if(pom>0)return 1;
if(pom<0)return 0;
if(pta.x==0)return pta.y>ptb.y;
return pta.x<ptb.x;
}
int n,w,h;
int128 hval[maxn][2];
void ispisi(pt a,pt b){
cout<<fixed<<setprecision(11)<<((double)a.x+b.x)/2<<" "<<((double)a.y+b.y)/2<<" ";
}
bool nisu_uliniji(ptt a,ptt b){
if(a.ff.x==a.ss.x && a.ss.x==b.ff.x && b.ff.x==b.ss.x)return false;
if(a.ff.y==a.ss.y && a.ss.y==b.ff.y && b.ff.y==b.ss.y)return false;
return true;
}
int128 get_rin128(mt19937_64 &gen){
ll pom=gen();
ll pom2=gen();
return (int128)((int128)pom^( ((int128)pom2) <<60));
}
void isp128(int128 x){
while(x){
cout<<(ll)(x%10)<<" ";
x/=10;
}
cout<<endl;
}
int main(){
///freopen("test.txt","r",stdin);
scanf("%d %d %d",&n,&w,&h);
mt19937_64 gen(10);
int128 currh=0;
int128 fullh=0;
vector<ptl>events;
for(int i=1;i<=n;i++){
pt a,b;
scanf("%lld %lld %lld %lld",&a.x,&a.y,&b.x,&b.y);
if(a.cross(b)<0)swap(a,b);
hval[i][0]=get_rin128(gen);
hval[i][1]=get_rin128(gen);
///isp128(hval[i][0]);
currh^=hval[i][0];
fullh^=hval[i][0];
fullh^=hval[i][1];
events.pb({a,hval[i][0]^hval[i][1]});
events.pb({b,hval[i][0]^hval[i][1]});
}
events.pb({pt(w,0),0});
events.pb({pt(0,h),0});
events.pb({pt(w,h),0});
sort(events.begin(),events.end(),cmp);
pt prv(0,0);
/// isto i kad zavrsis probaj sa 00
map<int128,vector<pair<pt,pt>> >mapa;
//mapa.reserve(4*n);
//mapa.max_load_factor(0.25);
for(int i=0;i<events.size();i++){
pt cpt=events[i].ff;
mapa[currh].pb({prv,cpt});
currh^=events[i].ss;
prv=cpt;
}
mapa[currh].pb({prv,pt(0,0)});
pt reza1,reza2,rezb1,rezb2;
bool flag=0;
for(auto it=mapa.begin();it!=mapa.end();it++){
int128 val=it->ff;
if(mapa.find(fullh^val)!=mapa.end()){
assert((fullh^val)!=val);
vector<ptt>&aa=it->ss;
vector<ptt>&bb=mapa[fullh^val];
for(int i=0;i<aa.size();i++){
for(int j=0;j<bb.size();j++){
if(nisu_uliniji(aa[i],bb[i])){
reza1=aa[i].ff;
reza2=aa[i].ss;
rezb1=bb[i].ff;
rezb2=bb[i].ss;
flag=1;
break;
}
}
if(flag)break;
}
if(flag)break;
}
}
if(flag){
printf("1\n");
/*reza1.ispis();
reza2.ispis();
rezb1.ispis();
rezb2.ispis();*/
ispisi(reza1,reza2);
ispisi(rezb1,rezb2);
printf("\n");
}
else{
printf("2\n");
cout<<fixed<<setprecision(11)<<0<<" "<<0.5<<" "<<(double)w-0.5<<" "<<h<<endl;
cout<<fixed<<setprecision(11)<<w<<" "<<0.5<<" "<<0.5<<" "<<h<<endl;
}
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 1ms
memory: 4040kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 3844kb
Test #3:
score: 0
Accepted
time: 1ms
memory: 3812kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 3952kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 4084kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 3884kb
Test #7:
score: 0
Accepted
time: 1ms
memory: 3860kb
Test #8:
score: 0
Accepted
time: 0ms
memory: 3868kb
Test #9:
score: 0
Accepted
time: 386ms
memory: 81472kb
Test #10:
score: 0
Accepted
time: 382ms
memory: 81360kb
Test #11:
score: 0
Accepted
time: 520ms
memory: 96780kb
Test #12:
score: 0
Accepted
time: 369ms
memory: 77612kb
Test #13:
score: 0
Accepted
time: 406ms
memory: 83084kb
Test #14:
score: 0
Accepted
time: 602ms
memory: 97444kb
Test #15:
score: 0
Accepted
time: 427ms
memory: 76904kb
Test #16:
score: 0
Accepted
time: 472ms
memory: 97764kb
Test #17:
score: 0
Accepted
time: 602ms
memory: 97888kb
Test #18:
score: 0
Accepted
time: 416ms
memory: 82420kb
Test #19:
score: 0
Accepted
time: 602ms
memory: 98892kb
Test #20:
score: 0
Accepted
time: 474ms
memory: 98332kb
Test #21:
score: 0
Accepted
time: 618ms
memory: 98980kb
Test #22:
score: 0
Accepted
time: 400ms
memory: 82992kb
Test #23:
score: 0
Accepted
time: 480ms
memory: 98916kb
Test #24:
score: 0
Accepted
time: 2725ms
memory: 379604kb
Test #25:
score: 0
Accepted
time: 3283ms
memory: 379684kb
Test #26:
score: 0
Accepted
time: 0ms
memory: 3956kb
Test #27:
score: 0
Accepted
time: 0ms
memory: 3872kb
Test #28:
score: 0
Accepted
time: 1ms
memory: 3960kb
Test #29:
score: 0
Accepted
time: 4ms
memory: 4988kb
Test #30:
score: 0
Accepted
time: 31ms
memory: 13464kb
Test #31:
score: 0
Accepted
time: 2754ms
memory: 329640kb
Test #32:
score: 0
Accepted
time: 3305ms
memory: 380396kb
Test #33:
score: 0
Accepted
time: 1ms
memory: 4044kb
Test #34:
score: 0
Accepted
time: 0ms
memory: 3904kb
Test #35:
score: 0
Accepted
time: 1ms
memory: 3948kb
Test #36:
score: 0
Accepted
time: 0ms
memory: 6576kb
Test #37:
score: 0
Accepted
time: 26ms
memory: 13580kb
Test #38:
score: 0
Accepted
time: 355ms
memory: 74760kb
Test #39:
score: 0
Accepted
time: 3051ms
memory: 378988kb
Test #40:
score: 0
Accepted
time: 1ms
memory: 3868kb
Test #41:
score: 0
Accepted
time: 1ms
memory: 3900kb
Test #42:
score: 0
Accepted
time: 1ms
memory: 3940kb
Test #43:
score: 0
Accepted
time: 9ms
memory: 6092kb
Test #44:
score: 0
Accepted
time: 125ms
memory: 31540kb
Test #45:
score: 0
Accepted
time: 2014ms
memory: 260492kb
Test #46:
score: 0
Accepted
time: 3228ms
memory: 381148kb
Test #47:
score: 0
Accepted
time: 1ms
memory: 3808kb
Test #48:
score: 0
Accepted
time: 0ms
memory: 3908kb
Test #49:
score: 0
Accepted
time: 0ms
memory: 3848kb
Test #50:
score: -100
Wrong Answer
time: 1ms
memory: 3848kb