#include <bits/stdc++.h>
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(), (x).end()
using namespace std;
const int BIT_SIZE = 1<<20;
int _bit[BIT_SIZE+1];
void bit_update(int p, int x) { for(int i=p; i<=BIT_SIZE; i+=i&-i) _bit[i] += x; }
int bit_query(int p) { int ret = 0; for(int i=p; i>0; i-=i&-i) ret += _bit[i]; return ret; }
int n, b[100010], a[200010], p1[100010], p2[100010], c1,c2;
bool chk[200010];
int getc1() {
while(c1 <=2*n-1 && chk[c1]) c1++;
return c1;
}
int getc2() {
while(c2 && chk[c2]) c2--;
return c2;
}
int main() {
scanf("%d", &n);
c1 = 1, c2 = 2*n-1;
for(int i=1; i<=n; i++) {
scanf("%d", b+i);
if(i == 1) {
chk[b[i]] = 1;
continue;
}
if(b[i-1] > b[i]) {
if(!chk[b[i]]) chk[p1[i] = b[i]] = 1, chk[p2[i] = getc1()] = 1;
else chk[p1[i] = getc1()] = 1, chk[p2[i] = getc1()] = 1;
} else if(b[i-1] < b[i]) {
if(!chk[b[i]]) {
chk[p1[i] = b[i]] = 1, chk[p2[i] = getc2()] = 1;
//printf("(1) i:%d %d %d\n", i, p1[i], p2[i]);
} else {
chk[p1[i] = getc2()] = 1, chk[p2[i] = getc2()] = 1;
//printf("(2) i:%d %d %d\n", i, p1[i], p2[i]);
}
} else {
chk[p1[i] = getc1()] = 1, chk[p2[i] = getc2()] = 1;
//printf("(3) i:%d %d %d\n", i, p1[i], p2[i]);
}
}
//printf("c1 : %d, c2 : %d\n", c1, c2);
a[1] = b[1];
for(int i=2; i<=n; i++) {
a[2*(i-1)] = p1[i];
a[2*(i-1)+1] = p2[i];
}
for(int i=1; i<2*n; i++) printf("%d ", a[i]);
return 0;
}
Compilation message
medians.cpp: In function 'int main()':
medians.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
medians.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", b+i);
~~~~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
496 KB |
Output is correct |
3 |
Correct |
2 ms |
496 KB |
Output is correct |
4 |
Correct |
3 ms |
496 KB |
Output is correct |
5 |
Correct |
3 ms |
620 KB |
Output is correct |
6 |
Correct |
3 ms |
620 KB |
Output is correct |
7 |
Correct |
3 ms |
620 KB |
Output is correct |
8 |
Correct |
4 ms |
620 KB |
Output is correct |
9 |
Correct |
3 ms |
620 KB |
Output is correct |
10 |
Correct |
3 ms |
620 KB |
Output is correct |
11 |
Correct |
2 ms |
620 KB |
Output is correct |
12 |
Correct |
4 ms |
620 KB |
Output is correct |
13 |
Correct |
4 ms |
624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
644 KB |
Output is correct |
2 |
Correct |
5 ms |
800 KB |
Output is correct |
3 |
Correct |
7 ms |
972 KB |
Output is correct |
4 |
Correct |
16 ms |
1436 KB |
Output is correct |
5 |
Correct |
27 ms |
2056 KB |
Output is correct |
6 |
Correct |
47 ms |
3520 KB |
Output is correct |
7 |
Correct |
59 ms |
5564 KB |
Output is correct |