oj.uz

Submission #368554

# Submission time Handle Problem Language Result Execution time Memory
368554 2021-02-20T05:20:17 Z cpp219 medians (balkan11_medians) C++14
100 / 100
 125 ms 12268 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 2e5 + 9;
const ll inf = 1e16 + 7;
typedef pair<int,int> LL;
vector<ll> ans;
set<ll> s;
ll n,b[N],was[N];

void Out(){
    for (auto i : s) cout<<i<<" ";
}

void DE(){
    ans.push_back(*prev(s.end())); s.erase(prev(s.end()));
    ans.push_back(*prev(s.end())); s.erase(prev(s.end()));
}

void DS(){
    ans.push_back(*s.begin()),s.erase(s.begin());
    ans.push_back(*s.begin()),s.erase(s.begin());
}

int main(){
    //ios_base::sync_with_stdio(0);
    //cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>n;
    for (ll i = 1;i <= 2*n - 1;i++) s.insert(i);
    for (ll i = 1;i <= n;i++) cin>>b[i],s.erase(b[i]);
    ans.push_back(b[1]); was[b[1]] = 1;
    for (ll i = 2;i <= n;i++){
        if (!was[b[i]]) ans.push_back(b[i]); //Out(); cout<<" x ";
        if (was[b[i]]){
            if (b[i - 1] > b[i]) DS();
            if (b[i - 1] < b[i]) DE();
            if (b[i - 1] == b[i]){
                ans.push_back(*s.begin()),s.erase(s.begin());
                ans.push_back(*prev(s.end())),s.erase(prev(s.end()));
            }
        }
        else if (b[i - 1] > b[i]) ans.push_back(*s.begin()),s.erase(s.begin());
        else if (b[i - 1] < b[i]) ans.push_back(*prev(s.end())),s.erase(prev(s.end()));
        was[b[i]] = 1; //Out(); cout<<"\n";
    }
    //exit(0);
    //for (auto i : s) cout<<i<<" "; exit(0);
    for (auto i : ans) cout<<i<<" ";
}

Compilation message

medians.cpp: In function 'int main()':
medians.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   33 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
65.0 / 65.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 4 ms 748 KB Output is correct
3 Correct 12 ms 1516 KB Output is correct
4 Correct 21 ms 2432 KB Output is correct
5 Correct 54 ms 4204 KB Output is correct
6 Correct 95 ms 8172 KB Output is correct
7 Correct 125 ms 12268 KB Output is correct