#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#ifdef dremix
#define p(x) cerr<<#x<<" = "<<x<<endl;
#define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
#define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
#define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
#define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
#define p(x)
#define p2(x,y)
#define pp(x)
#define pv(x)
#define ppv(x)
#endif
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 1e18;
const int MOD = 1e9+9;
const int N = 3e5+1;
int valid(int n, int arr[]){
bool v[N]={};
int i;
int idx = -1;
for(i=0;i<n;i++){
if(v[arr[i]])
return 0;
v[arr[i]]=1;
if(arr[i]<=n)idx = i;
}
if(idx==-1)return 1;
int curr = arr[idx];
for(i=0;i<n;i++){
if(arr[idx]<=n && arr[idx]!=curr)return 0;
curr++;
idx++;
if(curr>n)curr-=n;
idx%=n;
}
return 1;
}
int replacement(int n, int arr[], int ans[]){
int pos = 0,curr = n+1,idx,maxi = 0;
int i;
int one = -1;
vector<pi> seq;
for(i=0;i<n;i++){
if(arr[i]<=n)one = i;
else seq.push_back({arr[i],i});
if(arr[i]>maxi){
maxi = arr[i];
idx = i;
}
}
sort(all(seq));
int prev[n];
int val;
if(one==-1){
one = 0;
val = 1;
}
else
val = arr[one];
for(i=0;i<n;i++){
prev[one] = val;
val++;
one++;
if(val>n)val-=n;
one%=n;
}
for(auto x : seq){
while(curr!=x.F){
ans[pos] = prev[idx];
prev[idx] = curr;
curr++;
pos++;
}
ans[pos] = prev[x.S];
prev[x.S] = curr;
pos++;
curr++;
}
return pos;
}
int countReplacement(int n, int arr[]){
if(!valid(n,arr))return 0;
ll ans = 1;
vector<int> big;
int i;
for(i=0;i<n;i++)
if(arr[i]>n)big.push_back(arr[i]);
sort(all(big));
reverse(all(big));
//int pos = 0;
int curr = n+1;
while(big.size()){
if(curr==big.back())big.pop_back();
else ans = (ans*(ll)big.size())%MOD;
curr++;
}
return ans;
}
Compilation message
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:57:28: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
57 | int pos = 0,curr = n+1,idx,maxi = 0;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
640 KB |
Output is correct |
2 |
Correct |
1 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
640 KB |
Output is correct |
4 |
Correct |
1 ms |
640 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
640 KB |
Output is correct |
2 |
Correct |
1 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
640 KB |
Output is correct |
4 |
Correct |
1 ms |
640 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
6 ms |
768 KB |
Output is correct |
7 |
Correct |
14 ms |
896 KB |
Output is correct |
8 |
Correct |
11 ms |
896 KB |
Output is correct |
9 |
Correct |
4 ms |
640 KB |
Output is correct |
10 |
Correct |
12 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
640 KB |
Output is correct |
2 |
Correct |
1 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
640 KB |
Output is correct |
4 |
Correct |
1 ms |
640 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
6 ms |
768 KB |
Output is correct |
7 |
Correct |
13 ms |
896 KB |
Output is correct |
8 |
Correct |
11 ms |
896 KB |
Output is correct |
9 |
Correct |
4 ms |
640 KB |
Output is correct |
10 |
Correct |
14 ms |
896 KB |
Output is correct |
11 |
Correct |
1 ms |
640 KB |
Output is correct |
12 |
Correct |
1 ms |
640 KB |
Output is correct |
13 |
Correct |
7 ms |
768 KB |
Output is correct |
14 |
Correct |
1 ms |
640 KB |
Output is correct |
15 |
Correct |
15 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
14 ms |
896 KB |
Output is correct |
12 |
Correct |
13 ms |
1024 KB |
Output is correct |
13 |
Correct |
17 ms |
1416 KB |
Output is correct |
14 |
Correct |
11 ms |
896 KB |
Output is correct |
15 |
Correct |
24 ms |
2296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
640 KB |
Output is correct |
2 |
Correct |
1 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
640 KB |
Output is correct |
2 |
Correct |
1 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
640 KB |
Output is correct |
4 |
Correct |
1 ms |
640 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
1 ms |
640 KB |
Output is correct |
7 |
Correct |
1 ms |
640 KB |
Output is correct |
8 |
Correct |
1 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
640 KB |
Output is correct |
2 |
Correct |
1 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
640 KB |
Output is correct |
4 |
Correct |
1 ms |
640 KB |
Output is correct |
5 |
Correct |
0 ms |
640 KB |
Output is correct |
6 |
Correct |
0 ms |
640 KB |
Output is correct |
7 |
Correct |
1 ms |
640 KB |
Output is correct |
8 |
Correct |
1 ms |
640 KB |
Output is correct |
9 |
Correct |
20 ms |
1280 KB |
Output is correct |
10 |
Correct |
15 ms |
1280 KB |
Output is correct |
11 |
Correct |
7 ms |
896 KB |
Output is correct |
12 |
Correct |
7 ms |
896 KB |
Output is correct |
13 |
Incorrect |
3 ms |
640 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
640 KB |
Output is correct |
2 |
Correct |
1 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
640 KB |
Output is correct |
4 |
Correct |
1 ms |
640 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
1 ms |
768 KB |
Output is correct |
7 |
Correct |
1 ms |
640 KB |
Output is correct |
8 |
Correct |
1 ms |
640 KB |
Output is correct |
9 |
Correct |
18 ms |
1280 KB |
Output is correct |
10 |
Correct |
16 ms |
1408 KB |
Output is correct |
11 |
Correct |
7 ms |
896 KB |
Output is correct |
12 |
Correct |
8 ms |
896 KB |
Output is correct |
13 |
Incorrect |
3 ms |
640 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |