| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 962373 | IUA_Hasin | Gondola (IOI14_gondola) | 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>
#define endl "\n"
#define yeap cout<<"YES"<<endl
#define nope cout<<"NO"<<endl
#define ll long long
using namespace std;
const ll N = 1e9+5;
ll vis[N];
ll vec[N];
int valid(int n, int inputSeq[])
{
ll mn = 300000;
ll mx = -1;
ll mnind = 0;
ll status = 1;
for(int i=0; i<n; i++){
ll a = inputSeq[i];
if(a<mn){
mn = a;
mnind = i;
}
mx = max(mx, a);
vis[a]++;
if(vis[a]>1){
status = -1;
}
}
if(status==-1){
return 0;
} else {
if(mn>=n){
return 1;
} else {
ll cnt = 0;
ll ind = mnind;
ll temp = mn;
while(cnt<n){
ll temp1 = ind%n;
if(inputSeq[temp1]<=n){
if(inputSeq[temp1]!=temp){
status = -1;
break;
}
cnt++;
ind++;
temp++;
} else {
cnt++;
ind++;
temp++;
}
}
if(status==-1){
return 0;
} else {
return 1;
}
}
}
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
ll mx = -1;
ll mn = 300000;
for(int i=0; i<n; i++){
ll a = gondolaSeq[i];
vis[a] = 1;
mx = max(mx, a);
mn = min(mn, a);
}
if(mx==n){
return 0;
} else {
if(mn>n){
for(int i=0; i<n; i++){
ll a = gondolaSeq[i];
vec[a] = i+1;
}
ll cnt = 0;
ll cnt1 = n;
for(int i=n+1; i<=mx; i++){
ll b = vec[i];
if(vis[i]==1){
replacementSeq[cnt] = b;
cnt++;
cnt1++;
while(cnt1<i){
replacementSeq[cnt] = cnt1;
cnt++;
cnt1++;
}
}
}
return cnt;
} else {
ll mnind;
for(int i=0; i<n; i++){
if(gondolaSeq[i]==mn){
mnind = i;
break;
}
}
ll cntt = 0;
ll temp1 = mn;
ll temp2 = mnind;
while(cntt<n){
ll a = temp1%n;
ll b = temp2%n;
ll c = gondolaSeq[b];
if(a==0){
a = n;
}
vec[c] = a;
temp1++;
temp2++;
cntt++;
}
ll cnt = 0;
ll cnt1 = n;
for(int i=n+1; i<=mx; i++){
ll b = vec[i];
if(vis[i]==1){
replacementSeq[cnt] = b;
cnt++;
cnt1++;
while(cnt1<i){
replacementSeq[cnt] = cnt1;
cnt++;
cnt1++;
}
}
}
return cnt;
}
}
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
ll status = valid(n, inputSeq);
if(status==0){
return 0;
} else {
ll big_count = 0;
ll small_count = 0;
ll mn = 300000;
int mx = -1;
for(int i=0; i<n; i++){
mx = max(mx, inputSeq[i]);
if(inputSeq[i]>n){
big_count++;
}
}
if(mx==n){
return 1;
} else if(mx==n+1){
return 1;
} else if(mx==n+2){
return 1;
} else if(mx==n+3){
if(vis[n+1]==1){
return 1;
} else {
return 2;
}
} else {
if(big_count==1){
return 1;
} else if(big_count==2){
ll ans = 0;
ll a;
for(int i=n+1; i<=250; i++){
if(vis[i]==1){
a = i-n-1;
break;
}
}
ll M = 1000000009;
ll b = 1;
for(int i=0; i<a; i++){
b = b*2;
b = b%M;
}
return b;
} else if(big_count==3){
ll ans = 0;
ll tt = 0;
ll a, b;
ll temp;
for(int i=n+1; i<=250; i++){
if(vis[i]==1){
if(tt==0){
a = i-n-1;
tt++;
temp = i;
// cout<<i<<endl;
} else {
b = i-temp-1;
// cout<<i<<endl;
break;
}
}
}
ll M = 1e9+9;
ll c = 1;
ll d = 1;
for(int i=0; i<a; i++){
c = c*3;
c = c%M;
}
for(int i=0; i<b; i++){
d = d*2;
d = d%M;
}
// cout<<a<<" "<<b<<endl;
// cout<<c<<" "<<d<<endl;
ans = c*d;
ans = ans%M;
return ans;
} else {
sort(inputSeq, inputSeq+n);
vector<pair<ll, ll>> v;
ll pp = big_count;
ll temp = n+1;
for(int i=0; i<n; i++){
ll a = inputSeq[i];
if(a>n){
v.push_back({a-temp, pp});
pp--;
temp = a+1;
}
}
// for(int i=0; i<v.size(); i++){
// cout << v[i].first << " " << v[i].second << endl;
// }
vector<ll> v1;
ll M = 1e9+9;
for(int i=0; i<v.size(); i++){
ll a = v[i].first;
ll b = v[i].second;
ll c = 1;
for(int i=0; i<a; i++){
c = (c*b)%M;
c = c%M;
}
c = c%M;
v1.push_back(c);
}
ll ans = 1;
for(int i=0; i<v1.size(); i++){
ll temp1, temp2;
if(ans>500000004){
temp1 = ans-M;
} else {
temp1 = ans;
}
if(v1[i]>500000004){
temp2 = v1[i]-M;
} else {
temp2 = v1[i];
}
ans = ((temp1%M)*(temp2%M))%M;
ans = ans%M;
// ans = ans%M;
// v1[i] = v1[i]%M;
// ans = ans*v1[i];
// ans = ans%M;
}
if(ans<0){
ans = ans+M;
}
return ans;
}
}
}
}