Submission #60484

#TimeUsernameProblemLanguageResultExecution timeMemory
60484junodevelopermedians (balkan11_medians)C++17
100 / 100
59 ms5564 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...