QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297540 | #7560. Computer Network | Mag1sk | ML | 0ms | 0kb | C++17 | 1.8kb | 2024-01-04 18:23:10 | 2024-01-04 18:23:10 |
answer
#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int N = 1e6+5;
const int inf=1e18;
#define PII pair<int,int>
int a[N],b[N];
PII c[N];
int p_a[N],p_b[N];
int tot=inf;
int n;
int now=0;
bool flag=0;
void dfs()
{
// cout<<tot<<"\n";
if(a[1]<=b[1]){
int cntt=0;
for(int i=2;i<=n;i++){
if(a[i]-a[i-1]){
cntt++;
}
}
if(cntt==n-1){
tot=min(tot,now+b[1]-a[1]);
}
}
vector<int>aa(n+1);
for(int i=1;i<=n;i++) aa[i]=a[i];
bool ok=true;
for(int i=2;i<=n;i++){
int x=a[i]/2-a[i-1]/2;
if(x<p_b[i]){
ok=false;
}
}
if(ok){
for(int i=1;i<=n;i++){
a[i]/=2;
}
now++;
dfs();
now--;
for(int i=1;i<=n;i++){
a[i]=aa[i];
}
}
ok=true;
for(int i=2;i<=n;i++){
int x=(a[i]+1)/2-(a[i-1]+1)/2;
if(x<p_b[i]){
ok=false;
}
}
if(ok){
for(int i=1;i<=n;i++){
a[i]=(a[i]+1)/2;
}
now+=2;
dfs();
now-=2;
for(int i=1;i<=n;i++){
a[i]=aa[i];
}
}
}
bool solve() {
cin>>n;
for(int i=1;i<=n;i++ )cin>>a[i];
for(int i=1;i<=n;i++){
cin>>b[i];
c[i]={a[i],b[i]};
}
sort(c+1,c+1+n);
for(int i=2;i<=n;i++){
if(c[i].second<c[i-1].second) return false;
}
p_a[1]=c[1].first,a[1]=c[1].first,b[1]=c[1].second;
for(int i=2;i<=n;i++){
a[i]=c[i].first,b[i]=c[i].second;
p_a[i]=c[i].first;
p_b[i]=c[i].second-c[i-1].second;
}
dfs();
return true;
}
signed main() {
solve();
if(flag){
cout<<tot<<'\n';
}else{
cout<<-1<<"\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Memory Limit Exceeded
input:
5 1 2 3 4 5 6 6 6 6 7