#include "gondola.h"
//#include "grader.cpp"
#include <set>
#include <vector>
#include <cstring>
#include <assert.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 3e5 + 5;
namespace Valid
{
bool seen[MAXN];
bool sortedL[MAXN], sortedR[MAXN];
void fillSeen(int n, int a[], int maxVal)
{
for(int i = 0;i<=maxVal;i++)
{
seen[i] = false;
}
for(int i = 0;i<n;i++)
{
seen[ a[i] ] = true;
}
}
bool check(int n, int a[], int relevant)
{
int maxVal = 0;
for(int i = 0;i<n;i++)
{
maxVal = max(maxVal, a[i]);
sortedL[i] = sortedR[i] = false;
}
for(int i = 0;i<=maxVal;i++)
{
seen[i] = false;
}
for(int i = 0;i<n;i++)
{
if(seen[ a[i] ]==true) return false;
seen[ a[i] ] = true;
}
sortedL[0] = true;
for(int i = 1;i<n;i++)
{
if(a[i]>relevant) sortedL[i] = sortedL[i-1];
else sortedL[i] = (sortedL[i-1]&(a[i-1]<a[i]));
}
sortedR[n-1] = true;
for(int i = n-2;i>=0;i--)
{
if(a[i]>relevant) sortedR[i] = sortedR[i+1];
else sortedR[i] = (sortedR[i+1]&(a[i]<a[i+1]));
}
if(sortedL[n-1]==true && (a[n-1]==n || (a[n-1]>relevant && seen[n]==false))) return true;
for(int i = 0;i<n-1;i++)
{
if(sortedL[i]==true && sortedR[i+1]==true)
{
if(a[i]>relevant || a[i+1]>relevant)
{
if((a[i]>relevant && seen[n]==false) && (a[i+1]>relevant && seen[1]==false))
{
return true;
}
}
else
{
if(a[i]==n && a[i+1]==1)
{
return true;
}
}
}
}
return false;
}
};
namespace Replacement
{
vector <int> constructSlow(int n, int a[])
{
int maxVal = 0;
for(int i = 0;i<n;i++) maxVal = max(maxVal, a[i]);
vector <int> answer;
for(int num = maxVal;num>=n+1;num--)
{
int ind = -1;
for(int i = 0;i<n;i++)
{
if(a[i]==num)
{
ind = i;
break;
}
}
bool found = false;
Valid::fillSeen(n, a, num);
assert(Valid::seen[num]==true);
for(int x = num-1;x>=1;x--)
{
if(Valid::seen[x]==false)
{
a[ind] = x;
if(Valid::check(n, a, num-2)==true)
{
found = true;
answer.push_back(x);
break;
}
a[ind] = num;
}
}
//assert(found==true);
}
reverse(answer.begin(), answer.end());
return answer;
}
};
int valid(int n, int inputSeq[])
{
return Valid::check(n, inputSeq, n);
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector <int> answer = Replacement::constructSlow(n, gondolaSeq);
for(int i = 0;i<answer.size();i++)
{
replacementSeq[i] = answer[i];
//assert(answer[i]<=n+i);
}
return answer.size();
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
Compilation message
gondola.cpp: In function 'std::vector<int> Replacement::constructSlow(int, int*)':
gondola.cpp:112:18: warning: variable 'found' set but not used [-Wunused-but-set-variable]
112 | bool found = false;
| ^~~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:153:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | for(int i = 0;i<answer.size();i++)
| ~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 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 |
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 |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
6 ms |
640 KB |
Output is correct |
7 |
Correct |
13 ms |
896 KB |
Output is correct |
8 |
Correct |
10 ms |
768 KB |
Output is correct |
9 |
Correct |
4 ms |
512 KB |
Output is correct |
10 |
Correct |
12 ms |
840 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 |
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 |
6 ms |
640 KB |
Output is correct |
7 |
Correct |
13 ms |
896 KB |
Output is correct |
8 |
Correct |
10 ms |
768 KB |
Output is correct |
9 |
Correct |
3 ms |
512 KB |
Output is correct |
10 |
Correct |
12 ms |
896 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
6 ms |
768 KB |
Output is correct |
14 |
Correct |
0 ms |
384 KB |
Output is correct |
15 |
Correct |
14 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
288 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
256 KB |
Integer -3 violates the range [0, 1000000008] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
256 KB |
Integer -3 violates the range [0, 1000000008] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
384 KB |
Integer -3 violates the range [0, 1000000008] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
288 KB |
Integer -3 violates the range [0, 1000000008] |
2 |
Halted |
0 ms |
0 KB |
- |