#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
using namespace std;
const int MAXN = (int) 1e5;
int arr[MAXN + 1];
pair <int, int> sol[MAXN + 1];
bool vis[MAXN + 1];
bool cmp1(const int &a, const int &b) {
return sol[a].first > sol[b].first;
}
bool cmp2(const int &a, const int &b) {
return sol[a].second < sol[b].second;
}
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, n;
ios::sync_with_stdio(false);
cin >> n;
for(i = 1; i <= n; i++) {
cin >> arr[i];
sol[i] = {1, 2 * n - 1};
}
sol[1] = {arr[1], arr[1]};
vis[arr[1]] = 1;
vector <int> ord1, ord2;
char flag = 0;
int p = 2;
for(i = 2; i <= n; i++) {
if(arr[i] > arr[i - 1]) {
if(flag) {
sol[p].first = sol[p + 1].first = arr[i] + 1;
ord1.push_back(p);
ord1.push_back(p + 1);
}
else { // flag == 0
sol[p] = {arr[i], arr[i]};
vis[arr[i]] = 1;
sol[p + 1].first = arr[i] + 1;
}
flag |= 2;
}
if(arr[i] < arr[i - 1]) {
if(flag) {
sol[p].second = sol[p + 1].second = arr[i] - 1;
ord2.push_back(p);
ord2.push_back(p + 1);
}
else { // flag == 0
sol[p] = {arr[i], arr[i]};
vis[arr[i]] = 1;
sol[p + 1].second = arr[i] - 1;
}
flag |= 1;
}
if(arr[i] == arr[i - 1]) {
sol[p].first = arr[i] + 1;
sol[p + 1].second = arr[i] - 1;
flag = 3;
ord1.push_back(p);
ord2.push_back(p + 1);
}
p += 2;
}
sort(ord1.begin(), ord1.end(), cmp1);
sort(ord2.begin(), ord2.end(), cmp2);
int val = 2 * n - 1;
for(auto it : ord1) {
while(vis[val] == 1) {
val--;
}
vis[val] = 1;
sol[it].first = val;
}
val = 1;
for(auto it : ord2) {
while(vis[val] == 1) {
val++;
}
vis[val] = 1;
sol[it].first = val;
}
for(i = 1; i < 2 * n; i++) {
cout << sol[i].first << " ";
}
//cin.close();
//cout.close();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
504 KB |
Not a permutation |
| 3 |
Incorrect |
2 ms |
516 KB |
Not a permutation |
| 4 |
Incorrect |
2 ms |
516 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
544 KB |
Not a permutation |
| 6 |
Incorrect |
2 ms |
736 KB |
Not a permutation |
| 7 |
Incorrect |
2 ms |
736 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
736 KB |
Not a permutation |
| 9 |
Incorrect |
2 ms |
736 KB |
Not a permutation |
| 10 |
Incorrect |
3 ms |
768 KB |
Not a permutation |
| 11 |
Incorrect |
2 ms |
772 KB |
Output isn't correct |
| 12 |
Incorrect |
4 ms |
772 KB |
Not a permutation |
| 13 |
Incorrect |
2 ms |
772 KB |
Not a permutation |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
832 KB |
Not a permutation |
| 2 |
Incorrect |
4 ms |
860 KB |
Output isn't correct |
| 3 |
Incorrect |
6 ms |
1152 KB |
Not a permutation |
| 4 |
Incorrect |
9 ms |
1576 KB |
Not a permutation |
| 5 |
Incorrect |
17 ms |
2568 KB |
Output isn't correct |
| 6 |
Incorrect |
32 ms |
4176 KB |
Integer 16900548 violates the range [1, 127999] |
| 7 |
Runtime error |
24 ms |
6056 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
