#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
#define mp make_pair
const int maxl = 25e4 + 5;
const int mod = 1e9 + 7;
int valid(int n, int inputSeq[])
{
int root = -1;
vector<int> cnt(maxl,0);
for(int i = 0 ; i < n ; ++i){
if(inputSeq[i] <= n){
root = i;
break;
}
}
if(root == -1)return 1;
for(int j = (root + 1) % n , i = inputSeq[root] ; j != root ; j = (j + 1) % n , i = i % n + 1){
if(cnt[inputSeq[j]]++ == 1)return 0;
if(inputSeq[j] <= n && inputSeq[j] != i){
return 0;
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
assert(valid(n,gondolaSeq));
vector<ii> a;
for(int i = 0 ; i < n ; ++i){
if(gondolaSeq[i] > n)a.push_back(mp(gondolaSeq[i],i));
}
sort(a.begin(),a.end());
int now = 0;
int l = 0;
vector<int> avai , pos(maxl);
int root = -1;
for(int i = 0 ; i < n ; ++i){
if(gondolaSeq[i] <= n){
root = i;
break;
}
}
// printf("%d",root);
for(int i = (root == -1 ? 1 : gondolaSeq[root]) , j = (root == -1 ? 0 : root) , cnt = n ; cnt-- ; j = (j + 1) % n , i = i % n + 1){
pos[i] = j;
if(gondolaSeq[j] != i){
gondolaSeq[j] = i;
avai.push_back(i);
}
}
int res = 1;
for(int j = n + 1 ; now < a.size() ; ++j){
if(a[now].first == j){
// printf("%d\n", gondolaSeq[a[now].second]);
replacementSeq[l++] = gondolaSeq[a[now].second];
avai.erase(find(avai.begin(),avai.end(),gondolaSeq[a[now].second]));
// cerr << gondolaSeq[a[now].second] << endl;
++now;
}else{
replacementSeq[l++] = avai.back();
gondolaSeq[pos[avai.back()]] = j;
pos[j] = pos[avai.back()];
avai.back() = j;
res = (ll)res * avai.size() % mod;
}
}
for(int i = 1 ; i <= n ; ++i)res = res * i % mod;
return l;
}
//----------------------
int countReplacement(int n, int gondolaSeq[])
{
if(valid(n,gondolaSeq) == 0)return 0;
vector<ii> a;
for(int i = 0 ; i < n ; ++i){
if(gondolaSeq[i] > n)a.push_back(mp(gondolaSeq[i],i));
}
sort(a.begin(),a.end());
int now = 0;
int l = 0;
vector<int> avai , pos(maxl);
int root = -1;
for(int i = 0 ; i < n ; ++i){
if(gondolaSeq[i] <= n){
root = i;
break;
}
}
// printf("%d",root);
for(int i = (root == -1 ? 1 : gondolaSeq[root]) , j = (root == -1 ? 0 : root) , cnt = n ; cnt-- ; j = (j + 1) % n , i = i % n + 1){
pos[i] = j;
if(gondolaSeq[j] != i){
gondolaSeq[j] = i;
avai.push_back(i);
}
}
int res = 1;
for(int j = n + 1 ; now < a.size() ; ++j){
if(a[now].first == j){
// printf("%d\n", gondolaSeq[a[now].second]);
// replacementSeq[l++] = gondolaSeq[a[now].second];
avai.erase(find(avai.begin(),avai.end(),gondolaSeq[a[now].second]));
// cerr << gondolaSeq[a[now].second] << endl;
++now;
}else{
// replacementSeq[l++] = avai.back();
gondolaSeq[pos[avai.back()]] = j;
pos[j] = pos[avai.back()];
avai.back() = j;
res = (ll)res * avai.size() % mod;
}
}
if(root == -1)for(int i = 1 ; i <= n ; ++i)res = res * i % mod;
return res;
}
Compilation message
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:61:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = n + 1 ; now < a.size() ; ++j){
~~~~^~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:109:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = n + 1 ; now < a.size() ; ++j){
~~~~^~~~~~~~~~
gondola.cpp:91:9: warning: unused variable 'l' [-Wunused-variable]
int l = 0;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1280 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1280 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1280 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
