oj.uz

Submission #1108187

# Submission time Handle Problem Language Result Execution time Memory
1108187 2024-11-03T08:48:41 Z mispertion Measures (CEOI22_measures) C++17
59 / 100
 414 ms 14668 KB 
#include<bits/stdc++.h>

using namespace std;
#pragma GCC optimize("O1")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
#define F first
#define S second

const ld PI = 3.1415926535;
const int N = 5e5 + 2;
const int M = 1e7 + 1;
int mod = 998244353;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;

int mult(int a, int b) {
    return a * 1LL * b % mod;
}

int sum(int a, int b) {
    if (a + b < 0)
        return a + b + mod;
    if (a + b >= mod)
        return a + b - mod;
    return a + b;
}


ll binpow(ll a, ll n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1) {
        return binpow(a, n - 1) * a % mod;
    } else {
        ll b = binpow(a, n / 2);
        return b * b % mod;
    }
}

int n, m;
ld d;
vector<ld> x;

ld getans(){
    ld cur = x[0], ca = 0;
    for(int i = 1; i < x.size(); i++){
        if(x[i] + ca - cur >= d){
            ld nx;
            if(x[i] - cur >= d){
                nx = max(x[i] - ca, cur + d);
            }else{
                nx = cur + d;
            }
            cur = nx;
            continue;
        }
        ld ad = (d - x[i] - ca + cur) / 2;
        cur = cur - ad + d;
        ca += ad;
    }
    return ca;
}

vector<ld> getansd(){
    vector<ld> ret = {0};
    ld cur = x[0], ca = 0;
    for(int i = 1; i < x.size(); i++){
        if(x[i] + ca - cur >= d){
            ld nx;
            if(x[i] - cur >= d){
                nx = max(x[i] - ca, cur + d);
            }else{
                nx = cur + d;
            }
            cur = nx;
            ret.push_back(ca);
            continue;
        }
        ld ad = (d - x[i] - ca + cur) / 2;
        cur = cur - ad + d;
        ca += ad;
        ret.push_back(ca);
    }
    return ret;
}

void solve() {
    cin >> n >> m >> d;
    for(int i = 1; i <= n; i++){
        int ps;
        cin >> ps;
        x.push_back((ld)ps);
    }
    if(n == 0){
        for(int i = 1; i <= m; i++){
            int ps;
            cin >> ps;
            x.push_back((ld)ps);
        }
        sort(x.begin(), x.end());
        vector<ld> ret = getansd();
        for(auto e : ret){
            ll ans = e * 2;
            if(ans % 2 == 0){
                cout << ans / 2 << ' ';
            }else{
                cout << fixed << setprecision(1) << (ld)ans / 2 << ' ';
            }
        }
        return;
    }
    for(int i = 1; i <= m; i++){
        int ps;
        cin >> ps;
        x.push_back((ld)ps);
        sort(x.begin(), x.end());
        ll ans = getans() * 2;
        if(ans % 2 == 0){
            cout << ans / 2 << ' ';
        }else{
            cout << fixed << setprecision(1) << (ld)ans / 2 << ' ';
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Compilation message

Main.cpp: In function 'ld getans()':
Main.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i = 1; i < x.size(); i++){
      |                    ~~^~~~~~~~~~
Main.cpp: In function 'std::vector<long double> getansd()':
Main.cpp:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i = 1; i < x.size(); i++){
      |                    ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 3 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 3 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 257 ms 6600 KB Output is correct
10 Correct 399 ms 6600 KB Output is correct
11 Correct 146 ms 6600 KB Output is correct
12 Correct 414 ms 6600 KB Output is correct
13 Correct 121 ms 6600 KB Output is correct
14 Correct 243 ms 6612 KB Output is correct
15 Correct 232 ms 6768 KB Output is correct
16 Correct 115 ms 6600 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 14268 KB Output is correct
2 Correct 87 ms 14524 KB Output is correct
3 Correct 89 ms 14520 KB Output is correct
4 Correct 41 ms 14524 KB Output is correct
5 Correct 66 ms 14524 KB Output is correct
6 Correct 76 ms 14580 KB Output is correct
7 Correct 101 ms 14544 KB Output is correct
8 Correct 75 ms 14668 KB Output is correct
9 Correct 81 ms 14532 KB Output is correct
10 Correct 92 ms 14552 KB Output is correct
11 Correct 101 ms 14532 KB Output is correct
12 Correct 87 ms 14532 KB Output is correct
13 Correct 75 ms 14524 KB Output is correct
14 Correct 67 ms 14628 KB Output is correct
15 Correct 86 ms 14532 KB Output is correct
16 Correct 76 ms 14268 KB Output is correct
17 Correct 64 ms 14628 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 14268 KB Output is correct
2 Correct 87 ms 14524 KB Output is correct
3 Correct 89 ms 14520 KB Output is correct
4 Correct 41 ms 14524 KB Output is correct
5 Correct 66 ms 14524 KB Output is correct
6 Correct 76 ms 14580 KB Output is correct
7 Correct 101 ms 14544 KB Output is correct
8 Correct 75 ms 14668 KB Output is correct
9 Correct 81 ms 14532 KB Output is correct
10 Correct 92 ms 14552 KB Output is correct
11 Correct 101 ms 14532 KB Output is correct
12 Correct 87 ms 14532 KB Output is correct
13 Correct 75 ms 14524 KB Output is correct
14 Correct 67 ms 14628 KB Output is correct
15 Correct 86 ms 14532 KB Output is correct
16 Correct 76 ms 14268 KB Output is correct
17 Correct 64 ms 14628 KB Output is correct
18 Incorrect 118 ms 14524 KB Output isn't correct
19 Halted 0 ms 0 KB -