| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 245898 | uacoder123 | 곤돌라 (IOI14_gondola) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
int valid(int n, int inputSeq[])
{
lli p=-1;
for(lli i=0;i<n;++i)
{
if(inputSeq[i]<=n)
{
p=i;
break;
}
}
lli ch=0,v=inputSeq[p]-1;
if(v==0)
v=n;
for(lli i=p-1;i>=0;--i)
{
if(v==0)
v=n;
if(inputSeq[i]<=n&&inputSeq[i]!=v)
{
ch=1;
break;
}
v--;
}
v=inputSeq[p]+1;
if(v==n+1)
v=1;
for(lli i=p+1;i<n;++i)
{
if(v==n+1)
v=1;
if(inputSeq[i]<=n&&inputSeq[i]!=v)
{
ch=1;
break;
}
v++;
}
sort(inputSeq,inputSeq+n);
for(int i=1;i<n;++i)
{
if(inputSeq[i]==inputSeq[i-1])
ch=1;
}
return(!ch);
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
lli p=-1;
lli x=0,v=n+1,val;
lli varr[n],val1=1;
for(lli i=0;i<n;++i)
{
if(gondolaSeq[i]<=n)
{
p=i;
break;
}
}
vector<ii> v1;
if(p!=-1)
{
val1=gondolaSeq[p]-1;
varr[p]=gondolaSeq[p];
for(lli i=p-1;i>=0;--i)
{
if(val1==0)
val1=n;
varr[i]=val1;
val1--;
}
val1=gondolaSeq[p]+1;
for(lli i=p+1;i<n;++i)
{
if(val1>n)
val1=1;
varr[i]=val1;
val1++;
}
}
for(lli i=0;i<n;++i)
{
if(p==-1)
val=i+1;
else
{
val=varr[i];
}
if(gondolaSeq[i]>n)
v1.pb(mp(gondolaSeq[i],val));
}
sort(all(v1));
for(lli i=0;i<v1.size();++i)
{
replacementSeq[x]=v1[i].S;
x++;
while(v<v1[i].F)
{
replacementSeq[x]=v;
x++;
v++;
}
v++;
}
return(x);
}
lli tel(lli p,lli n)
{
lli b=0,ans=1,a=n;
while((1LL<<b)<=n)
{
if(bit(p,b))
ans=(ans*a)%1000000007;
a=(a*a)*1000000007;
b++;
}
return(ans);
}
int countReplacement(int n, int inputSeq[])
{
lli p=-1;
for(lli i=0;i<n;++i)
{
if(inputSeq[i]<=n)
{
p=i;
break;
}
}
if(!valid(n,inputSeq))
return(0);
lli co=0,ans=1,l=n;
for(lli i=0;i<n;++i)
{
if(inputSeq[i]>n)
co++;
}
sort(inputSeq,inputSeq+n);
for(lli i=0;i<n;++i)
{
if(inputSeq[i]<=n)
continue;
cout<<co<<' '<<inputSeq[i]<<' '<<l<<' '<<ans<<endl;
ans=(ans*tel(inputSeq[i]-l-1,co))%1000000007;
l=inputSeq[i];
co--;
}
return(ans);
}
int gondolaSequence[100001];
int replacementSequence[250001];
int main()
{
int i, n, tag;
int nr;
assert(scanf("%d", &tag)==1);
assert(scanf("%d", &n)==1);
for(i=0;i< n;i++)
assert( scanf("%d", &gondolaSequence[i]) ==1);
switch (tag){
case 1: case 2: case 3:
printf("%d\n", valid(n, gondolaSequence));
break;
case 4: case 5: case 6:
nr = replacement(n, gondolaSequence, replacementSequence);
printf("%d ", nr);
if (nr > 0)
{
for (i=0; i<nr-1; i++)
printf("%d ", replacementSequence[i]);
printf("%d\n", replacementSequence[nr-1]);
}
else printf("\n");
break;
case 7: case 8: case 9: case 10:
printf("%d\n", countReplacement(n, gondolaSequence));
break;
}
return 0;
}