| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 127720 | tinjyu | 곤돌라 (IOI14_gondola) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "gondola.h"
#include <iostream>
using namespace std;
int a[100005],b[100005],n;
int qs(int s,int e)
{
if(s>=e)return 0;
int l=s,r=e,mid=(a[l]+a[r])/2;
while(l<=r)
{
while(a[l]<mid)l++;
while(a[r]>mid)r--;
if(l<=r)
{
swap(a[l],a[r]);
swap(b[l],b[r]);
l++;
r--;
}
}
qs(s,r);
qs(l,e);
}
int valid(int N, int a[])
{
n=N;
int tmp=-1,mi=500005,tag[500005];
for(int i=0;i<=500000;i++)tag[i]=0;
for(int i=0;i<n;i++)
{
if(tag[a[i]]==1)return 0;
tag[a[i]]++;
}
for(int i=0;i<n;i++)
if(a[i]<=n && a[i]<mi)
{
tmp=i;
mi=a[i];
}
if(tmp==-1)return 1;
int p=n-1,i=tmp,t=mi;
while(p--)
{
i++;
i%=n;
t++;
if(a[i]<=n && a[i]!=t)return 0;
}
return 1;
}
//----------------------
int replacement(int N, int gondolaSeq[], int replacementSeq[])
{
n=N;
int t=-1;
for(int i=0;i<n;i++)a[i]=gondolaSeq[i];
for(int i=0;i<n;i++)
{
if(a[i]<=n)
{
t=i;
break;
}
}
if(t==-1)for(int i=0;i<n;i++)b[i]=i+1;
else
{
b[t]=a[t];
int now=a[t],i=t;
int p=n-1;
while(p--)
{
i++;
i%=n;
now=now%n+1;
b[i]=now;
}
}
//for(int i=0;i<n;i++)cout<<a[i]<<" "<<b[i]<<endl;
qs(0,n-1);
//for(int i=0;i<n;i++)cout<<a[i]<<" "<<b[i]<<endl;
int ans1=0,x=n+1;
for(int i=0;i<n;i++)
{
while(a[i]!=b[i])
{
replacementSeq[ans1]=b[i];
b[i]=x;
ans1++;
x++;
}
}
return ans1;
}
//----------------------
int countReplacement(int N, int inputSeq[])
{
if(valid(int N, int inpuSeq[])==0)return 0;
return 1;
}