이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "books.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int boss[1000005],mx[1000005],mi[1000005];
int finds(int x)
{
if(boss[x]==x) return x;
return boss[x]=finds(boss[x]);
}
void Union(int a,int b)
{
a=finds(a),b=finds(b);
boss[a]=b,mx[b]=max(mx[b],mx[a]),mi[b]=min(mi[b],mi[a]);
}
long long minimum_walk(vector<int> p, int s)
{
ll ans=0,ls=-1,L=0,R=0;
for(int i=0;i<p.size();++i) boss[i]=i,mx[i]=i,mi[i]=i;
for(int i=s;p[i]==i;++i)
++R;
if(R==p.size()-s) R=-1;
for(int i=s;p[i]==i;--i)
++L;
if(L==s+1) L=-1;
for(int i=0;i<p.size();++i)
Union(i,p[i]);
for(int i=0;i<p.size();++i)
ans+=abs(p[i]-i);
if(ans==0) return 0;
for(int i=0;i<p.size();)
if(finds(i),mx[boss[i]]==mi[boss[i]]) ++i;
else
{
if(~ls) ans+=(mi[boss[i]]-ls)*2;
for(ls=mx[finds(i)];i<=ls;++i)
ls=max((ll)mx[finds(i)],ls);
}
finds(s);
if(mi[boss[s]]==mx[boss[s]])
if(!~L) ans+=R*2;
else if(!~R) ans+=L*2;
else;
else
ans+=min(L*2,R*2);
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<p.size();++i) boss[i]=i,mx[i]=i,mi[i]=i;
~^~~~~~~~~
books.cpp:38:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(R==p.size()-s) R=-1;
~^~~~~~~~~~~~
books.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<p.size();++i)
~^~~~~~~~~
books.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<p.size();++i)
~^~~~~~~~~
books.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<p.size();)
~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |