QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#366060 | #7184. Transport Pluses | Giga_Cronos# | WA | 0ms | 3896kb | C++20 | 4.2kb | 2024-03-25 04:51:12 | 2024-03-25 04:51:13 |
Judging History
answer
///Giga_Cronos Template from UH Top
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops", "omit-frame-pointer", "inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#pragma GCC option("arch=native", "no-zero-upper") // Enable AVX
using namespace std;
///Macros
#define int long long
#define pb push_back
#define fs first
#define sc second
#define pf push_front
#define all(x) x.begin() , x.end()
#define rall(x) x.rbegin() , x.rend()
#define sz(x) (int)(x.size())
#define mid ((L+R)/2)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector< pii > vpii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
typedef pair<vi,vi> pvv;
typedef __int128_t int128;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int ui;
///Constraints:
const int inf = ((1ll<<31ll)-1ll);
const long long INF = (((1ll<<60ll)-1ll)*2ll)+1ll;
const ull mod=998244353;
const ld pi = acos(-1);
const ld eps=1e-8;
/// Functions:
#define lg2(x) 31 - __builtin_clz(x)
#define lg2ll(x) 63ll - __builtin_clzll(x)
#define lgx(x,b) ( log(x) / log(b) )
/*#include<ext/pb_ds/assoc_container.hpp> // Common file
#include<ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
//comenta el define long long int
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// find_by_order
// order_of_key */
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
/// Quick Pow------------------------------------------------
int qpow(int a, int b) {
int res = 1;
for (; b; b /= 2, a = (a*a)%mod) {
if (b % 2) {
res =(res*a)%mod;
}
}
return res;
}
int qpow(int a, int b,int mod) {
int res = 1;
for (; b; b /= 2, a = (a*a)%mod) {
if (b % 2) {
res =(res*a)%mod;
}
}
return res;
}
///Inverso Modular
int InverM(int a,int b)
{
int eso=a%b;
if(eso==0)
return 0;
int ans=(1-(int128)b*InverM(b,eso))/eso;
if(ans<0)
ans+=b;
return ans;
}
const int MAXN=200'005;
/// Variables-----------------------------------------------
int n,m,q,k;
ld Dist(pii A,pii B){
B.fs-=A.fs;
B.sc-=A.sc;
return sqrt(B.fs*B.fs+B.sc*B.sc);
}
pii nearest(pii A,pii B){
if(abs(A.fs-B.fs)<abs(A.sc-B.sc)){
return {B.fs,A.sc};
}else{
return {A.fs,B.sc};
}
}
void problem()
{
int t;
cin>>n>>t;
vpii A(n+2);
cin>>A[0].fs>>A[0].sc;
cin>>A[n+1].fs>>A[n+1].sc;
for(int i=1;i<=n;i++){
cin>>A[i].fs>>A[i].sc;
}
pair<ld,vector<pair<int,pii>>> Ans;
Ans={Dist(A[0],A[n+1]),{{0,A[n+1]}} };
int closer1=1;
int closer2=1;
for(int i=1;i<=n;i++){
if(min(abs(A[0].fs-A[i].fs),abs(A[0].sc-A[i].sc))<min(abs(A[0].fs-A[closer1].fs),abs(A[0].sc-A[closer1].sc))){
closer1=i;
}
if(min(abs(A[n+1].fs-A[i].fs),abs(A[n+1].sc-A[i].sc))<min(abs(A[n+1].fs-A[closer2].fs),abs(A[n+1].sc-A[closer2].sc))){
closer2=i;
}
}
Ans=min(Ans,{2*t+min(abs(A[0].fs-A[closer1].fs),abs(A[0].sc-A[closer1].sc))+min(abs(A[n+1].fs-A[closer2].fs),abs(A[n+1].sc-A[closer2].sc))
, { {0,nearest(A[0],A[closer1])}
,{closer1,{A[closer1].fs,A[closer2].sc}}
,{closer2,nearest(A[n+1],A[closer2])}
,{0,A[n+1]}}
});
for(int i=1;i<=n;i++){
Ans=min(Ans,{t+min(abs(A[0].fs-A[i].fs),abs(A[0].sc-A[i].sc))+min(abs(A[n+1].fs-A[i].fs),abs(A[n+1].sc-A[i].sc)),
{{0,nearest(A[0],A[i])}
,{i,nearest(A[n+1],A[i])}
,{0,A[n+1]}
}
}
);
}
cout<<Ans.fs<<'\n';
cout<<sz(Ans.sc)<<'\n';
for(auto p:Ans.sc){
cout<<p.fs<<' '<<p.sc.fs<<' '<<p.sc.sc<<'\n';
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed);
cout.precision(12);
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
int tc=1;
//cin>>tc;
while(tc--)
{
problem();
cout<<'\n';
}
}
///Tips
//Busqueda Binaria
//Precomputing
//Dinamic Programming
//Revisar constraints
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3844kb
input:
1 2 1 1 5 3 6 2
output:
4.000000000000 3 0 1 2 1 5 2 0 5 3
result:
ok correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
2 1 1 1 6 1 1 3 6 3
output:
2.000000000000 4 0 1 1 1 1 3 2 6 1 0 6 1
result:
ok correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
0 0 1 1 1 1
output:
0.000000000000 1 0 1 1
result:
ok correct
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3896kb
input:
0 0 100 100 0 0
output:
100.000000000000 4 0 100 0 1 0 0 1 0 0 0 0 0
result:
wrong answer Integer 1 violates the range [0, 0]