oj.uz

Submission #480731

# Submission time Handle Problem Language Result Execution time Memory
480731 2021-10-18T01:33:46 Z TranGiaHuy1508 medians (balkan11_medians) C++17
100 / 100
 27 ms 4804 KB 
// C++ Template

#include "bits/stdc++.h"
using namespace std;

// Type
typedef long long ll;
typedef long double ld;

// Pair/Vector
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

// Macro
#define stat(x) x && cout << "YES\n" || cout << "NO\n";
#ifdef LOCAL
    #define debug(x) cout << #x << " = " << x << "\n";
#else
    #define debug(x) ;
#endif

// Custom output
template <class A, class B>
ostream& operator << (ostream& out, pair<A, B> x){
    out << "(" << x.first << ", " << x.second << ")";
    return out;
}

template <class T>
ostream& operator << (ostream& out, vector<T> x){
    out << "[";
    for (int i=0; i<x.size(); i++){
        if (i) out << ", ";
        out << x[i];
    }
    out << "]";
    return out;
}

void fastio(string finp = "", string fout = ""){
    if (fopen(finp.c_str(), "r")){
        freopen(finp.c_str(), "r", stdin);
        freopen(fout.c_str(), "w", stdout);
    }
}

// Const
const int interactive = 0;
const ld PI = acos(-1.0);
const ll allmod[2] = {int(1e9)+7, 998244353};
const ll mod = allmod[0];
const ll maxn = 2e5;
const ll inf = 1e18;
const int multitest = 0;

#define int long long

vi v, res;

void main_program(){
    int n; cin >> n;
    v.assign(n*2, 0);
    int crr; cin >> crr;
    v[crr] = 1;
    res.push_back(crr);
    int l = 1, r = 2*n-1;

    for (int i=0; i<n-1; i++){
    	int x; cin >> x;

    	if (x == crr){
    		while (v[l]) l++;
    		while (v[r]) r--;

    		res.push_back(l);
    		res.push_back(r);

    		v[l] = v[r] = 1;
    	}
    	else if (x > crr){
    		if (!v[x]){
    			v[x] = 1;
    			res.push_back(x);
    		}
    		else{
    			while (v[r]) r--;
    			res.push_back(r);
    			v[r] = 1;
    		}

    		while (v[r]) r--;
    		res.push_back(r);
    		v[r] = 1;
    	}
    	else{
    		if (!v[x]){
    			v[x] = 1;
    			res.push_back(x);
    		}
    		else{
    			while (v[l]) l++;
    			res.push_back(l);
    			v[l] = 1;
    		}

    		while (v[l]) l++;
    		res.push_back(l);
    		v[l] = 1;
    	}

    	crr = x;
    }

    for (int i=0; i<res.size(); i++) cout << res[i] << " ";
}

void pre_main(){
    
}

signed main(){

    #ifdef LOCAL
        auto start_time = chrono::high_resolution_clock::now();
    #endif

    if (!interactive) ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
        fastio(".inp", ".out");
    #endif

    int t = 1;
    if (multitest) cin >> t;
    pre_main();
    while (t--) main_program();

    #ifdef LOCAL
        auto end_time = chrono::high_resolution_clock::now();
        double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
        cout << "\n[" << duration << "ms]\n";
    #endif
}

Compilation message

medians.cpp: In function 'void main_program()':
medians.cpp:116:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for (int i=0; i<res.size(); i++) cout << res[i] << " ";
      |                   ~^~~~~~~~~~~
medians.cpp: In function 'int main()':
medians.cpp:129:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  129 |     if (!interactive) ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
      |     ^~
medians.cpp:129:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  129 |     if (!interactive) ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
      |                                                     ^~~
medians.cpp: In function 'void fastio(std::string, std::string)':
medians.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen(finp.c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
medians.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen(fout.c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
65.0 / 65.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 5 ms 1104 KB Output is correct
5 Correct 10 ms 1828 KB Output is correct
6 Correct 20 ms 3232 KB Output is correct
7 Correct 27 ms 4804 KB Output is correct