QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#297538#7560. Computer NetworkMag1skML 0ms0kbC++171.8kb2024-01-04 18:22:382024-01-04 18:22:39

Judging History

你现在查看的是最新测评结果

  • [2024-01-04 18:22:39]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-01-04 18:22:38]
  • 提交

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";
    }
}

詳細信息

Test #1:

score: 0
Memory Limit Exceeded

input:

5
1 2 3 4 5
6 6 6 6 7

output:


result: