oj.uz

답안 #202449

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202449 2020-02-16T07:31:47 Z quocnguyen1012 중앙값 배열 (balkan11_medians) C++14
100 / 100
 37 ms 3704 KB 
#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

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.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 380 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 480 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 8 ms 580 KB Output is correct
4 Correct 10 ms 888 KB Output is correct
5 Correct 15 ms 1404 KB Output is correct
6 Correct 25 ms 2424 KB Output is correct
7 Correct 37 ms 3704 KB Output is correct