QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297489 | #7560. Computer Network | Saanteye# | WA | 1ms | 9636kb | C++14 | 2.0kb | 2024-01-04 16:13:16 | 2024-01-04 16:13:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
const int inf=1e9;
#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";
vector<int>aa(n+1);
for(int i=1;i<=n;i++) aa[i]=a[i];
bool ok=true;
int cntt=0;
for(int i=2;i<=n;i++){
int x=a[i]/2-a[i-1]/2;
if(x<p_b[i]){
ok=false;
}else if(x==p_b[i]&&a[1]/2<=b[1]){
cntt++;
}
}
if(cntt==n-1){
flag=1;
tot=min(tot,now+1+b[1]-a[1]/2);
return;
}
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;
cntt=0;
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;
}else if(x==p_b[i]&&(a[1]+1)/2<=b[1]){
cntt++;
}
}
if(cntt==n-1){
flag=1;
tot=min(tot,now+2+b[1]-(a[1]+1)/2);
return;
}
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;
}
int 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: 100
Accepted
time: 0ms
memory: 9564kb
input:
5 1 2 3 4 5 6 6 6 6 7
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 1ms
memory: 9564kb
input:
3 2 3 4 1 2 3
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 9616kb
input:
2 65536 65537 1 2
output:
32
result:
ok 1 number(s): "32"
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 9636kb
input:
1 0 28
output:
29
result:
wrong answer 1st numbers differ - expected: '28', found: '29'