Submission #202449

#	Time	Username	Problem	Language	Result	Execution time	Memory
202449		quocnguyen1012	medians (balkan11_medians)	C++14	100 / 100	37 ms	3704 KiB

medians

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 3e5 + 5;
const ll llinf = 1e18;

int a[maxn], b[maxn];
bool vis[maxn];
int N;
int st, en;

void addst(int pos)
{
  while (vis[st]) ++st;
  b[pos] = st;
  vis[st] = true;
}

void adden(int pos)
{
  while (vis[en]) --en;
  b[pos] = en;
  vis[en] = true;
  //cerr << pos <<' ' << en << '\n';
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N;
  for (int i = 1; i <= N; ++i){
    cin >> a[i];
  }
  st = 1, en = 2 * N - 1;
  b[1] = a[1];
  vis[a[1]] = true;
  for (int i = 2; i <= N; ++i){
    if (a[i] == a[i - 1]){
      addst(2 * i - 2);
      adden(2 * i - 1);
    }
    else if (a[i] > a[i - 1]){
      if (vis[a[i]] == false){
        vis[a[i]] = true;
        b[i * 2 - 2] = a[i];
        adden(2 * i - 1);
        //cerr << en << '\n';
        //cerr << 2 * i - 1 << ' ' << b[2 * i - 1] << '\n';
      }
      else{
        adden(2 * i - 2);
        adden(2 * i - 1);
      }
    }
    else{
      if (vis[a[i]] == false){
        vis[a[i]] = true;
        b[i * 2 - 2] = a[i];
        addst(2 * i - 1);
      }
      else{
        addst(2 * i - 2);
        addst(2 * i - 1);
      }
    }
  }
  for (int i = 1; i <= 2 * N - 1; ++i){
    cout << b[i] << ' ' ;
  }
}

Compilation message (stderr)

medians.cpp: In function 'int main()':
medians.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
medians.cpp:39:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 65 / 65
• Subtask 2: 35 / 35