#include "gondola.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
typedef int ll;
typedef long long lll;
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
int valid(int n, int inputSeq[])
{
ll sus = -1;
set<ll> realsus;
FOR(i,0,n){
realsus.insert(inputSeq[i]);
if (inputSeq[i] <= n){
sus = i;
}
}
if (realsus.size() != n) return 0;
if (sus==-1) return 1;
ll cnt = inputSeq[sus];
FOR(i, sus, sus+n){
if (cnt > n) cnt -= n;
ll imp = i;
if (imp>=n) imp -= n;
if (inputSeq[imp] != cnt && inputSeq[imp] <= n) return 0;
cnt++;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector<ll> sussy(n);
ll sus = -1;
FOR(i,0,n){
if (gondolaSeq[i] <= n){
sus = i;
}
}
ll cnt = gondolaSeq[sus];
if (sus==-1) sus = 0, cnt = 1;
FOR(i,sus,sus+n){
if (cnt>n) cnt-=n;
sussy[i%n] = cnt;
cnt++;
}
ll maxi = -1;
ll maxpos = -1;
FOR(i,0,n){
if (gondolaSeq[i] > maxi){
maxpos = i;
maxi = max(maxi, gondolaSeq[i]);
}
}
vector<ll> stuff(maxi-n);
FOR(i,0,maxi-n) stuff[i] = -1;
FOR(i,0,n){
if (gondolaSeq[i] > n){
stuff[gondolaSeq[i]-n-1] = i;
}
}
FOR(i,0,maxi-n){
if (stuff[i] != -1){
replacementSeq[i] = sussy[stuff[i]];
sussy[stuff[i]] = i+n+1;
}else{
replacementSeq[i] = sussy[maxpos];
sussy[maxpos] = i+n+1;
}
}
return maxi-n;
}
//----------------------
unordered_map<ll,ll> cache;
lll fastexp(lll n, lll e, lll p){
if (e==0) return 1;
if (e==1) return n;
if (e==2) return n*n % p;
if (e%2==0){
lll a = fastexp(n, e/2, p);
return a*a%p;
}else{
lll a = fastexp(n, e-1, p);
return a*n%p;
}
}
int countReplacement(int n, int inputSeq[])
{
if (!valid(n, inputSeq)) return 0;
ll maxi = 0;
FOR(i,0,n) maxi = max(maxi, inputSeq[i]);
if (maxi <= n) return 1;
ll mini = 1000000000;
FOR(i,0,n) mini = min(mini, inputSeq[i]);
long long ans = 1;
if (mini > n) ans*= n;
ll sus = n;
unordered_set<ll> imp;
FOR(i,0,n) imp.insert(inputSeq[i]);
FOR(i,0,n) if (inputSeq[i] <= n) sus -= 1;
vector<ll> torn;
FOR(i,0,n) torn.push_back(inputSeq[i]);
torn.push_back(n);
sort(torn.begin(), torn.end());
FOR(i,1,n+1){
if (torn[i] <= n) continue;
ans *= max((lll) 1, fastexp(sus,torn[i]-torn[i-1]-1,1000000009));
ans %= 1000000009;
sus--;
}
return ans%1000000009;
}
Compilation message
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:30:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
30 | if (realsus.size() != n) return 0;
| ~~~~~~~~~~~~~~~^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
11 ms |
2132 KB |
Output is correct |
7 |
Correct |
22 ms |
3668 KB |
Output is correct |
8 |
Correct |
19 ms |
3988 KB |
Output is correct |
9 |
Correct |
5 ms |
1472 KB |
Output is correct |
10 |
Correct |
23 ms |
4460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
9 ms |
2132 KB |
Output is correct |
7 |
Correct |
22 ms |
3568 KB |
Output is correct |
8 |
Correct |
17 ms |
3916 KB |
Output is correct |
9 |
Correct |
6 ms |
1364 KB |
Output is correct |
10 |
Correct |
22 ms |
4480 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
12 ms |
2016 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
27 ms |
4564 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
7 ms |
844 KB |
Output is correct |
12 |
Correct |
8 ms |
988 KB |
Output is correct |
13 |
Correct |
10 ms |
1108 KB |
Output is correct |
14 |
Correct |
7 ms |
852 KB |
Output is correct |
15 |
Correct |
16 ms |
2108 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
39 ms |
4564 KB |
Output is correct |
10 |
Correct |
29 ms |
3540 KB |
Output is correct |
11 |
Correct |
10 ms |
1748 KB |
Output is correct |
12 |
Correct |
13 ms |
1876 KB |
Output is correct |
13 |
Correct |
3 ms |
596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
37 ms |
4496 KB |
Output is correct |
10 |
Correct |
30 ms |
3652 KB |
Output is correct |
11 |
Correct |
11 ms |
1748 KB |
Output is correct |
12 |
Correct |
13 ms |
1876 KB |
Output is correct |
13 |
Correct |
3 ms |
596 KB |
Output is correct |
14 |
Correct |
45 ms |
4832 KB |
Output is correct |
15 |
Correct |
55 ms |
7396 KB |
Output is correct |
16 |
Correct |
8 ms |
1492 KB |
Output is correct |
17 |
Correct |
37 ms |
4352 KB |
Output is correct |
18 |
Correct |
18 ms |
2644 KB |
Output is correct |