Submission #1352402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1352402		kiensosad	medians (balkan11_medians)	C++20	100 / 100	95 ms	18296 KiB

medians

/*https://oj.uz/problem/view/balkan11_medians*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>     
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
const int N = 1000000;
ordered_set s;
int m[N+2],b[N+2];
signed main(){
    #define task ""
    if(fopen(task ".inp", "r")){
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    vector<int> ans;
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    ans.push_back(b[1]);
    m[b[1]]=1;
    set<int> sett;
    for(int i=1;i<=2*n-1;i++){
        // s.insert(i);
        sett.insert(i);
    }
    sett.erase(b[1]);
    s.insert(b[1]);
    for(int i=2;i<=n;i++){
        int d=i-1-s.order_of_key(b[i]);
        if(m[b[i]]==0){
            ans.push_back(b[i]);
            m[b[i]]=1;
            s.insert(b[i]);
            sett.erase(b[i]);
            int t=0;
            if(d==1){
                auto it=sett.begin();
                t=*it;
                sett.erase(it);
            }
            else if(d==0){
                auto it=sett.end();
                it--;
                t=*it;
                sett.erase(it);
            }
            ans.push_back(t);
            m[t]=1;
            s.insert(t);
        }
        else{
            int u,v;
            if(d==2){
                auto it=sett.begin();
                u=*it;sett.erase(u);
                it=sett.begin();
                v=*it;sett.erase(v);
            }
            else if(d==1){
                auto it=sett.begin();
                u=*it;sett.erase(u);
                it=sett.end();it--;
                v=*it;sett.erase(v);
            }
            else{
                auto it=sett.end();it--;
                u=*it;sett.erase(u);
                it=sett.end(); it--;
                v=*it;sett.erase(v);
            }
            ans.push_back(u);ans.push_back(v);
            m[u]=m[v]=1;
            s.insert(u);s.insert(v);
        }
    }
    for(auto v:ans) cout<<v<<" ";
    return 0;
}

Compilation message (stderr)

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

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