/*input
2
3 4
*/
/**
Author: Kristopher Paul
Date Created: 15-05-2019
Contest Name:
_/ _/ _/_/_/_/ _/ _/_/_/_/
_/ _/ _/ _/ _/ _/
_/_/ _/_/_/_/ _/ _/_/_/_/
_/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/_/_/_/
**/
#include <gondola.h>
#include<bits/stdc++.h>
#define ll long long
//#define int ll
#define pb push_back
#define INF 0x3f3f3f3f //0x3f3f3f3f = 63
#define MOD 1000000009
#define mp make_pair
const double PI=3.141592653589793238462643383279502884197169399375105820974944;
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define umap unordered_map
#define pii pair<int,int>
#define F first
#define S second
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define itr :: iterator it
#define all(v) v.begin(),v.end()
#define WL(t) while(t--)
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define out(x) cout << #x << " is " << x << endl
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
ll ModExp(ll x,ll y,ll m){
ll res = 1;
x = x % m;
while (y > 0)
{
if (y & 1)
res = (res*x) % m;
y = y>>1;
x = (x*x) % m;
}
return res;
}
int valid(int n, int arr[]){
int mini = n+1;
int pos = n;
umap<int,int> cnt;
FOR(i,0,n){
cnt[arr[i]]++;
if(cnt[arr[i]] > 1){
return 0;
}
if(arr[i] < mini){
mini = arr[i];
pos = i;
}
}
if(mini > n){
return 1;
}
int to[n];
int val = arr[pos];
FOR(i,pos,n){
to[i] = val;
if(arr[i] <= n && arr[i] != to[i]){
return 0;
}
val++;
if(val == n+1){
val = 1;
}
}
FOR(i,0,pos){
to[i] = val;
if(arr[i] <= n && arr[i] != to[i]){
return 0;
}
val++;
if(val == n+1){
val = 1;
}
}
return 1;
}
int replacement(int n, int arr[], int replacementSeq[]){
int mini = n+1;
int pos = 0;
FOR(i,0,n){
if(arr[i] < mini){
mini = arr[i];
pos = i;
}
}
vector<pii> vec;
if(mini > n){
FOR(i,0,n){
vec.pb({arr[i],i+1});
}
}else{
int v = mini;
FOR(i,pos,n){
if(arr[i] > n){
vec.pb({arr[i],v});
}
v++;
if(v == n+1){
v = 1;
}
}
FOR(i,0,pos){
if(arr[i] > n){
vec.pb({arr[i],v});
}
v++;
if(v == n+1){
v = 1;
}
}
}
sort(vec.begin(),vec.end());
int st = n+1;
int ind = 0;
FOR(i,0,vec.size()){
int cur = vec[i].first;
int lv = vec[i].second;
FOR(j,st,cur+1){
replacementSeq[ind] = lv;
lv = j;
ind++;
}
st = cur+1;
}
return ind;
}
int countReplacement(int n, int arr[]){
if(!valid(n,arr)){
return 0;
}
int maxi = 0;
int mini = n+1;
int pos = 0;
FOR(i,0,n){
remax(maxi,arr[i]);
if(arr[i] < mini){
mini = arr[i];
pos = i;
}
}
if(maxi <= n){
return 1;
}
vector<int> vec;
FOR(i,0,n){
if(arr[i] > n){
vec.pb(arr[i]);
}
}
sort(vec.begin(),vec.end());
int st = n+1;
vector<ll> sz;
ll cur = 0;
FOR(i,0,vec.size()){
cur += vec[i]-st;
if(cur > 0){
sz.pb(cur);
}
st = vec[i]+1;
}
ll ans = 1;
int lv = 1;
FOR(i,0,sz.size()){
if(sz[i] < lv){
continue;
}
ans *= ModExp((sz.size()-i),(sz[i]-lv+1),MOD);
ans %= MOD;
lv = sz[i]+1;
}
if(mini > n){
ans *= n;
ans %= MOD;
}
ans %= MOD;
return ans;
}
/*
void solve(){
int n;
cin >> n;
int arr[n];
FOR(i,0,n){
cin >> arr[i];
}
cout << countReplacement(n,arr) << endl;
}
signed main(){
FastIO;
int t = 1;
// cin >> t;
WL(t){
solve();
}
}*/
Compilation message
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:25:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,a,b) for (int i = a; i < b; i++)
gondola.cpp:140:9:
FOR(i,0,vec.size()){
~~~~~~~~~~~~~~
gondola.cpp:140:5: note: in expansion of macro 'FOR'
FOR(i,0,vec.size()){
^~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:25:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,a,b) for (int i = a; i < b; i++)
gondola.cpp:180:9:
FOR(i,0,vec.size()){
~~~~~~~~~~~~~~
gondola.cpp:180:5: note: in expansion of macro 'FOR'
FOR(i,0,vec.size()){
^~~
gondola.cpp:25:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,a,b) for (int i = a; i < b; i++)
gondola.cpp:189:9:
FOR(i,0,sz.size()){
~~~~~~~~~~~~~
gondola.cpp:189:5: note: in expansion of macro 'FOR'
FOR(i,0,sz.size()){
^~~
gondola.cpp:159:9: warning: variable 'pos' set but not used [-Wunused-but-set-variable]
int pos = 0;
^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
3 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
316 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
11 ms |
2224 KB |
Output is correct |
7 |
Correct |
14 ms |
768 KB |
Output is correct |
8 |
Correct |
21 ms |
3984 KB |
Output is correct |
9 |
Correct |
8 ms |
1408 KB |
Output is correct |
10 |
Correct |
26 ms |
4428 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
11 ms |
2224 KB |
Output is correct |
7 |
Correct |
16 ms |
768 KB |
Output is correct |
8 |
Correct |
20 ms |
3984 KB |
Output is correct |
9 |
Correct |
8 ms |
1408 KB |
Output is correct |
10 |
Correct |
83 ms |
4360 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
256 KB |
Output is correct |
13 |
Correct |
12 ms |
1968 KB |
Output is correct |
14 |
Correct |
2 ms |
256 KB |
Output is correct |
15 |
Correct |
27 ms |
4232 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
384 KB |
Output is correct |
11 |
Correct |
10 ms |
640 KB |
Output is correct |
12 |
Correct |
12 ms |
640 KB |
Output is correct |
13 |
Correct |
23 ms |
1296 KB |
Output is correct |
14 |
Correct |
12 ms |
640 KB |
Output is correct |
15 |
Correct |
20 ms |
2288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
3 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
38 ms |
4104 KB |
Output is correct |
10 |
Correct |
37 ms |
3564 KB |
Output is correct |
11 |
Correct |
12 ms |
1408 KB |
Output is correct |
12 |
Correct |
20 ms |
1920 KB |
Output is correct |
13 |
Correct |
4 ms |
640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
34 ms |
3976 KB |
Output is correct |
10 |
Correct |
26 ms |
3592 KB |
Output is correct |
11 |
Correct |
10 ms |
1408 KB |
Output is correct |
12 |
Correct |
20 ms |
1920 KB |
Output is correct |
13 |
Correct |
5 ms |
768 KB |
Output is correct |
14 |
Correct |
43 ms |
4088 KB |
Output is correct |
15 |
Correct |
57 ms |
4460 KB |
Output is correct |
16 |
Correct |
11 ms |
1152 KB |
Output is correct |
17 |
Correct |
37 ms |
3496 KB |
Output is correct |
18 |
Correct |
20 ms |
1968 KB |
Output is correct |