| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 696883 | n0sk1ll | Gondola (IOI14_gondola) | C++14 | 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 <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
#define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
#define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
//const int mod = 1000000007;
//Note to self: Check for overflow
#include "gondola.h"
#define int li
const int mod=1'000'000'009;
int valid(int n, int a[])
{
set<int> gondola;
ff(i,0,n) gondola.insert(a[i]);
if ((int)gondola.size()!=n) return 0;
set<int> ost;
ff(i,0,n) if (a[i]<=n) ost.insert((a[i]+n-i)%n);
return ((int)ost.size()==1);
}
int gdet[356256];
int gdea[356256];
int og[300005];
int replacement(int n, int a[], int ans[])
{
ff(i,0,n) og[i]=a[i];
int p=0;
while (p<n && a[p]>n) p++;
if (p!=n)
{
ff(i,p+1,n) og[i]=(og[i-1]+1)%n;
ff(i,0,p) og[i]=(og[(i+n-1)%n]+1)%n;
}
else
{
ff(i,0,n) og[i]=i+1;
}
ff(i,0,n) if (og[i]==0) og[i]=n;
ff(i,0,n-1) if (og[i]==n && og[i+1]==n)
{
ff(j,0,n) og[j]=j+1;
break;
}
fff(i,0,350001) gdea[i]=-1,gdet[i]=-1;
ff(i,0,n) gdet[og[i]]=i;
ff(i,0,n) gdea[a[i]]=i;
int k=0;
bfff(i,0,350000) if (gdea[i]==-1) gdea[i]=gdea[i+1];
fff(i,n+1,350000) if (gdea[i]!=-1) ans[k++]=og[gdea[i]],og[gdea[i]]=i; else break;
return k;
}
int power(int a, int n)
{
li c=1;
while (n)
{
if (n&1) (c*=a)%=mod;
a=(li)a*a%mod,n>>=1;
}
return c;
}
int countReplacement(int n, int a[])
{
if (!valid(n,a)) return 0;
vector<int> add;
ff(i,0,n) if (a[i]>n) add.pb(a[i]);
sort(all(add));
if (add.empty()) return 1;
li ans=power((int)add.size(),add[0]-n-1);
ff(i,1,(int)add.size()) (ans*=power((int)add.size()-1,add[i]-add[i-1]-1))%=mod;
return ans;
}
/*int main()
{
FAST;
while (true){
int n; cin>>n;
int a[n];
ff(i,0,n) cin>>a[i];
int ans[251000];
ff(i,0,3*n) ans[i]=0;
cout<<replacement(n,a,ans)<<"\n";
ff(i,0,3*n) cout<<ans[i]<<" "; cout<<endl;
}
}*/