#include "gondola.h"
#include<iostream>
#include<algorithm>
#include<map>
#define ll long long
#define rep(i,a,b) for(int i = a;i < b;i++)
#define MAXNUM 250002
using namespace std;
ll go[MAXNUM],freq2[MAXNUM];
map < ll,ll > freq;
ll valid(ll n, ll inputSeq[])
{
ll mini = 0;
rep(i,0,n)
{
if(inputSeq[i] < inputSeq[mini])
{
mini = i;
}
freq[inputSeq[i]]++;
}
if(freq.size() != n)
return false;
ll cur = 1;
ll num = (inputSeq[mini] > n) ? 1 : inputSeq[mini];
rep(i,mini-num+1,mini+n-num+1)
{
ll x = (i+2*n)%n;
if(inputSeq[x] > n)
continue;
if(inputSeq[x] != cur)
{
return false;
}
cur++;
}
return true;
}
//----------------------
ll replacement(ll n, ll gondolaSeq[], ll replacementSeq[])
{
ll mini = 0;
ll maxi = 0;
rep(i,0,n)
{
if(gondolaSeq[i] < gondolaSeq[mini])
{
mini = i;
}
if(gondolaSeq[i] > gondolaSeq[maxi])
{
maxi = i;
}
}
ll num = (gondolaSeq[mini] > n) ? 1 : gondolaSeq[mini];
ll cur = 1;
rep(x,mini-num+1,mini+n-num+1)
{
ll i = (x+2*n)%n;
if(gondolaSeq[i] > n)
{
freq2[gondolaSeq[i]]++;
}
// cout << x << " " << gondolaSeq[i] << " " << cur<< endl;
go[gondolaSeq[i]] = cur;
cur++;
}
ll countt = 0;
ll prev = go[gondolaSeq[maxi]];
rep(i,n+1,gondolaSeq[maxi]+1)
{
if(i == gondolaSeq[maxi] || freq2[i] == 0)
{
replacementSeq[countt] = prev;
prev = i;
}
else
{
replacementSeq[countt] = go[i];
}
countt++;
}
return countt;
}
//----------------------
ll mod = 1000000009;
ll fast_expo(ll vasi,ll ek)
{
if(ek == 0)
return 1;
if(ek == 1)
return vasi;
unsigned ll x = fast_expo(vasi,ek/2);
x = (x*x)%mod;
if(ek%2==1)
{
x = (x*vasi)%mod;
}
return x;
}
ll countReplacement(ll n, ll inputSeq[])
{
ll countt = 0;
ll maxi = 0;
rep(i,0,n)
{
if(inputSeq[i] > n)
{
countt++;
}
if(inputSeq[i] > inputSeq[maxi])
{
maxi = i;
}
}
/*
if(countt == 0)
{
ll cur = 1;
rep(i,maxi+1,maxi+n+1)
{
ll x = i%n;
if(inputSeq[x] != cur)
{
return 0;
}
cur++;
}
}
*/
sort(inputSeq,inputSeq+n);
unsigned ll res = 1;
ll prev = n;
if(countt == n)
res = n;
rep(i,0,n)
{
if(inputSeq[i] <= n)
continue;
res = (res*fast_expo(countt%mod,inputSeq[i] - prev - 1))%mod;
prev = inputSeq[i];
countt--;
}
return res;
}
/*
int main()
{
ll q,n,ar[MAXNUM],res[MAXNUM];
cin >> q >> n;
rep(i,0,n)
{
cin >> ar[i];
}
if(q <= 3)
{
cout << valid(n,ar) << endl;
}
else if(q <= 6)
{
ll ans = replacement(n,ar,res);
cout << ans << " ";
rep(i,0,ans)
{
cout << res[i] << " ";
}
cout << endl;
}
else
{
cout << countReplacement(n,ar) << endl;
}
}
*/
Compilation message
gondola.cpp: In function 'long long int valid(long long int, long long int*)':
gondola.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(freq.size() != n)
~~~~~~~~~~~~^~~~
/tmp/ccElWIsK.o: In function `main':
grader.cpp:(.text.startup+0xc3): undefined reference to `countReplacement'
grader.cpp:(.text.startup+0xe2): undefined reference to `valid'
grader.cpp:(.text.startup+0x106): undefined reference to `replacement'
collect2: error: ld returned 1 exit status
