| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 589191 | BT21tata | Stations (IOI20_stations) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "gondola.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll MOD=1e9+9;
bool hp[250005];
int valid(int n, int a[])
{
int val=-1;
for(int i=0; i<n; i++)
{
if(a[i]<=n)
{
if(val==-1)
{
val=a[i]+1;
if(val==n+1) val=1;
}
else
{
if(a[i]!=val)
{
//cout<<i<<' '<<a[i]<<' '<<val<<endl;
return 0;
}
else
{
val=a[i]+1;
if(val==n+1) val=1;
}
}
}
else
{
if(hp[a[i]]) return 0;
hp[a[i]]=1;
if(val!=-1)
{
val++;
if(val==n+1) val=1;
}
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int rep=1, m=0;
for(int i=0; i<n; i++)
{
if(gondolaSeq[i]<=n)
{
rep=gondolaSeq[i];
for(int j=i-1; j>=0; j--)
{
rep--;
if(!rep) rep=n;
}
break;
}
}
multiset<pair<int, int>> s;
for(int i=0; i<n; i++)
{
if(rep!=gondolaSeq[i])
{
s.insert({gondolaSeq[i], rep});
}
rep++;
if(rep==n+1) rep=1;
}
int b=n+1;
while(s.size())
{
int need=(*s.begin()).first;
int hv=(*s.begin()).second;
s.erase(s.begin());
replacementSeq[m++]=hv;
hv=b++;
if(need!=hv) s.insert({need, hv});
}
return m;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
if(!valid(n, inputSeq)) return 0;
int rep=-1;
for(int i=0; i<n; i++)
{
if(inputSeq[i]<=n)
{
rep=inputSeq[i];
for(int j=i-1; j>=0; j--)
{
rep--;
if(!rep) rep=n;
}
break;
}
}
ll ans=1;
if(rep==-1)
{
rep=1;
ans*=n;
}
multiset<pair<int, int>> s;
for(int i=0; i<n; i++)
{
if(rep!=inputSeq[i])
{
s.insert({inputSeq[i], rep});
}
rep++;
if(rep==n+1) rep=1;
}
int b=n+1;
while(s.size())
{
int need=(*s.begin()).first;
int hv=(*s.begin()).second;
s.erase(s.begin());
hv=b++;
if(need!=hv) s.insert({need, hv}), ans*=1ll*s.size(), ans%=MOD;
}
return ans;
}