#include <iostream>
#include <bits/stdc++.h>
#define mod 1000000009
//#include "gondola.h"
using namespace std;
set<int> gond;
set<int> pok;
int step(int a,int b)
{
if(b==0)
return 1;
if(b%2==0)
return (step(a,b/2)%mod)*(step(a,b/2)%mod);
return (step(a,b/2)%mod)*(step(a,b/2)%mod)*(a%mod);
}
int valid(int n,int seq[])
{
int prvi=-1;
for(int i=0;i<n;i++)
{
if(seq[i]<=n)
{
prvi=i;
break;
}
}
if(prvi==-1)
{
for(int i=0;i<n;i++)
{
if(gond.find(seq[i])!=gond.end())
{
return 0;
}
gond.insert(seq[i]);
}
return 1;
}
int tren=seq[prvi];
for(int i=prvi+1;i<n;i++)
{
if(tren==n)
{
if(seq[i]!=1)
{
if(seq[i]<=n)
{
return 0;
}
if(gond.find(seq[i])!=gond.end())
{
return 0;
}
gond.insert(seq[i]);
}
tren=1;
}
else if(seq[i]!=tren+1)
{
if(seq[i]<=n)
{
return 0;
}
if(gond.find(seq[i])!=gond.end())
{
return 0;
}
gond.insert(seq[i]);
tren=tren+1;
}
else{
tren=tren+1;
}
}
for(int i=0;i<=prvi;i++)
{
if(tren==n)
{
if(seq[i]!=1)
{
if(seq[i]<=n)
{
return 0;
}
if(gond.find(seq[i])!=gond.end())
{
return 0;
}
gond.insert(seq[i]);
}
tren=1;
}
else if(seq[i]!=tren+1)
{
if(seq[i]<=n)
{
return 0;
}
if(gond.find(seq[i])!=gond.end())
{
return 0;
}
gond.insert(seq[i]);
tren=tren+1;
}
else{
tren=tren+1;
}
}
return 1;
}
int replacement(int n, int gondola[], int promena[])
{
int prvi=-1;
vector <pair<int,int>> v;
for(int i=0;i<n;i++)
{
if(gondola[i]<=n)
{
prvi=i;
break;
}
}
if(prvi==-1)
{
for(int i=0;i<n;i++)
{
v.push_back({gondola[i],i+1});
}
sort(v.begin(),v.end());
int tren=n+1;
int poz=0;
for(int i=0;i<v.size();i++)
{
promena[poz]=v[i].second;
poz++;
while(tren!=v[i].first)
{
promena[poz]=tren;
poz++;
tren++;
}
tren++;
}
return poz;
}
int next;
if(gondola[prvi]==n)
{
next=1;
}
else{
next=gondola[prvi]+1;
}
for(int i=prvi+1;i<n;i++)
{
if(gondola[i]!=next)
{
v.push_back({gondola[i],next});
}
if(next==n)
{
next=1;
}
else{
next++;
}
}
for(int i=0;i<prvi;i++)
{
if(gondola[i]!=next)
{
v.push_back({gondola[i],next});
}
if(next==n)
{
next=1;
}
else{
next++;
}
}
sort(v.begin(),v.end());
int tren=n+1;
int poz=0;
for(int i=0;i<v.size();i++)
{
promena[poz]=v[i].second;
poz++;
while(tren!=v[i].first)
{
promena[poz]=tren;
poz++;
tren++;
}
tren++;
}
return poz;
}
int countReplacement(int n, int seq[])
{
if(!valid(n,seq))
return 0;
int brpok=0;
int maks=0;
for(int i=0;i<n;i++)
{
if(seq[i]>n)
{
brpok++;
pok.insert(seq[i]);
}
maks=max(maks,seq[i]);
}
if(brpok==0)
return 1;
int stepen=0;
int ans=1;
for(int i=n+1;i<=maks;i++)
{
if(pok.find(i)!=pok.end())
{
ans=(ans*step(brpok,stepen)%mod);
brpok--;
stepen=0;
}
else{
stepen++;
}
}
return ans;
}
Compilation message
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:133:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for(int i=0;i<v.size();i++)
| ~^~~~~~~~~
gondola.cpp:186:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
186 | for(int i=0;i<v.size();i++)
| ~^~~~~~~~~
/tmp/ccRIZzWf.o: In function `main':
grader.cpp:(.text.startup+0xa2): undefined reference to `valid'
grader.cpp:(.text.startup+0xee): undefined reference to `countReplacement'
grader.cpp:(.text.startup+0x112): undefined reference to `replacement'
collect2: error: ld returned 1 exit status
