#include<bits/stdc++.h>
#include"xylophone.h"
using namespace std;
using ll=long long;
const ll inf=1e18;
void solve(int N)
{
vector<ll>D1(N),D2(N),dist(N+1,inf);
for(ll i=1;i<N;i++)D1[i]=query(i,i+1);
for(ll i=2;i<N;i++)D2[i]=query(i-1,i+1);
vector<array<ll,3>>edge;
for(ll i=1;i<N;i++)edge.push_back(array{i,i+1,D1[i]});
for(ll i=2;i<N;i++)if(D2[i]!=D1[i-1]+D1[i])edge.push_back(array{i-1,i+1,abs(D1[i]-D1[i-1])});
dist[1]=0;
for(ll t=0;t<N;t++)
for(auto[u,v,w]:edge)
{
dist[v]=min(dist[v],dist[u]+w);
dist[u]=min(dist[u],dist[v]+w);
}
ll mn=inf;
for(ll i=1;i<=N;i++)mn=min(mn,dist[i]);
for(ll i=1;i<=N;i++)dist[i]+=mn+1;
mn=inf;
ll mi=-1,mx=-inf,mxi=-1;
for(ll i=1;i<=N;i++)
{
if(mn>dist[i]){mn=dist[i];mi=i;}
if(mx<dist[i]){mx=dist[i];mxi=i;}
}
for(ll i=1;i<=N;i++)answer(i,mi>mxi ? dist[i]:N+1-dist[i]);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [7] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [7] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [7] |
2 |
Halted |
0 ms |
0 KB |
- |