oj.uz

Submission #770737

# Submission time Handle Problem Language Result Execution time Memory
770737 2023-07-01T20:23:55 Z emad234 medians (balkan11_medians) C++17
100 / 100
 19 ms 2936 KB 
#include <bits/stdc++.h>
#define all(v) ((v).bvin(),(v).end())
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const ll mxN = 2e6 + 3;
bool vis[mxN];
int b[mxN];
int a[mxN];
int mx,mn;
void pshmx(){
  while(vis[mx]){
    mx--;
  }
}void pshmn(){
  while(vis[mn]){
    mn++;
  }
}
signed main()
{
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int n;
  cin >>n;
  mx = 2 * n - 1;mn = 1;
  for(int i = 1;i <= n;i++) cin >> b[i];
  a[1] = b[1];
  vis[b[1]] = 1;
  pshmn();
  pshmx();
  for(int i = 2;i <= n;i++){
    int l = 2 * i - 2,r = 2 * i - 1;
    if(b[i - 1] < b[i]){
      if(!vis[b[i]]){
        a[l] = b[i];vis[a[l]] = 1;
      }
      else{
        pshmx();
        a[l] = mx;vis[mx] = 1;
        pshmx();
      }
      pshmx();
      a[r] = mx;vis[mx] = 1;
      pshmx();
    }
    if(b[i - 1] > b[i]){
      if(!vis[b[i]]){
        a[l] = b[i];vis[a[l]] = 1;
      }
      else{
        pshmn();
        a[l] = mn;vis[mn] = 1;
        pshmn();
      }
      pshmn();
      a[r] = mn;vis[mn] = 1;
      pshmn();
    }
    if(b[i - 1] == b[i]){
      pshmx();
      pshmn();
      a[l] = mn;vis[mn] = 1;
      a[r] = mx;vis[mx] = 1;
      pshmn();
      pshmx();
    }
  }
  for(int i = 1;i <= 2 * n - 1;i++){
    cout<<a[i]<<' ';
  }
}

Subtask #1
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 6 ms 1108 KB Output is correct
6 Correct 12 ms 1896 KB Output is correct
7 Correct 19 ms 2936 KB Output is correct