//#include "gondola.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
mt19937 rng(1);
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
return abs(temp) + l;
}
int n;
int valid(int N, int inputSeq[]){
set<int> se;
n = N;
for(int i = 0; i < n; i++) se.insert(inputSeq[i]);
if(se.size() < n) return 0;
ii ind = {-1, -1};
for(int i = 0; i < n; i++){
if(inputSeq[i] <= n){
ind = {i, inputSeq[i]};
break;
}
}
// no original gorillas
if(ind.fi < 0) return 1;
//set<int> se;
// check if other original gorillas are compatible
for(int i = ind.fi + 1; i < n; i++){
ind.se++;
if(ind.se > n) ind.se = 1;
if(inputSeq[i] <= n && inputSeq[i] != ind.se) return 0;
}
for(int i = 0; i < ind.fi; i++){
ind.se++;
if(ind.se > n) ind.se = 1;
if(inputSeq[i] <= n && inputSeq[i] != ind.se) return 0;
}
return 1;
}
int need[N];
int replacement(int N, int gondolaSeq[], int replacementSeq[]){
n = N;
for(int i = 0; i < n; i++) need[i] = i;
for(int i = 0; i < n; i++){
if(gondolaSeq[i] <= n){
int itr = gondolaSeq[i];
for(int j = i; j < n; j++){
need[j] = itr;
itr++;
if(itr > n) itr = 1;
}
for(int j = 0; j < i; j++){
need[j] = itr;
itr++;
if(itr > n) itr = 1;
}
break;
}
}
set<int> se;// se saves the numbers that are not in the conversation
ii mx = {-1, -1};
for(int i = 0; i < n; i++) mx = max(mx, {gondolaSeq[i], i});
for(int i = n + 1; i <= mx.fi; i++) se.insert(i);
for(int i = 0; i < n; i++) se.erase(gondolaSeq[i]);
mx.se = need[mx.se];// the original number
for(auto it : se){
// the next number replace the last number
replacementSeq[it - n - 1] = mx.se;
mx.se = it;
}
replacementSeq[mx.fi - n - 1] = mx.se;
for(int i = 0; i < n; i++){// other numbers just need to be fixed once
if(gondolaSeq[i] > n && gondolaSeq[i] != (mx.fi)){
replacementSeq[gondolaSeq[i] - n - 1] = need[i];
}
}
//for(int i = 0; i < mx.fi - n; i++) cout << replacementSeq[i] << " ";
//cout << "\n";
return mx.fi - n;
}
int countReplacement(int N, int inputSeq[]){
return 0;
}
/*
void process(){
int n;
cin >> n;
int arr[n], arr2[n];
for(int i = 0; i < n; i++) cin >> arr[i];
cout << replacement(n, arr, arr2) << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--) process();
}
*/
Compilation message
gondola.cpp:19:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
19 | const int oo = 1e18 + 7, mod = 1e9 + 7;
| ~~~~~^~~
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:34:15: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
34 | if(se.size() < n) return 0;
| ^
/usr/bin/ld: /tmp/cc0xZXdG.o: in function `main':
grader.cpp:(.text.startup+0xb6): undefined reference to `valid'
/usr/bin/ld: grader.cpp:(.text.startup+0x108): undefined reference to `countReplacement'
/usr/bin/ld: grader.cpp:(.text.startup+0x132): undefined reference to `replacement'
collect2: error: ld returned 1 exit status
