oj.uz

Submission #739915

# Submission time Handle Problem Language Result Execution time Memory
739915 2023-05-11T15:21:16 Z danikoynov Measures (CEOI22_measures) C++14
24 / 100
 404 ms 2804 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 4e5 + 10;

int n, m;
ll d, a[maxn], b[maxn];

bool check(double x)
{
    double last = -1e18;
    for (int i = 1; i <= n; i ++)
    {
        if (last + d > a[i] + x)
            return false;
        last = max(last + d, a[i] - x);
        //cout << last << " " << a[i] << endl;
    }
    return true;
}

void solve_query()
{
    sort(a + 1, a + n + 1);
    ll lf = 0, rf = 1e18;
    //cout << check(684538602442.5) << endl;
    //exit(0);
    while(lf <= rf)
    {
        ll mf = (lf + rf) / 2;
        //cout << lf << " " << rf << endl;
        if (check(mf))
            rf = mf - 1;
        else
            lf = mf + 1;
    }

    double ans = lf;
    if (ans > 0 && check(ans - 0.5))
    {
        ans = ans - 0.5;
        printf("%0.1f ", ans);
    }
    else
    {
        cout << (ll)(round(ans)) << " ";
    }
}
void solve()
{
    cin >> n >> m >> d;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    for (int i = 1; i <= m; i ++)
        cin >> b[i];

        bool sorted = true;
        for (int i = 2; i <= m; i ++)
        {
            if (b[i] < b[i - 1])
                sorted = false;
        }

        if (n == 0 && sorted)
        {
            cout << 0 << " ";
            double last = b[1];
            double p = 0;
            for (int i = 2; i <= m; i ++)
            {
                if (last + d > b[i] + p)
                {
                    ///cout << last + d << " " << p + b[i] << endl;

                    p = p + (double)((last + d - b[i] - p)) / 2.0;
                    last = last - (double)((last + d - b[i] - p)) / 2.0;
                }
                last = max(last + d, b[i] - p);
                if ((ll)(floor(p)) + 0.5 == p)
                    printf("%0.1f ", p);
                else
                    cout << (ll)(p) << " ";
            }
        }
        else
        {

    for (int i = 1; i <= m; i ++)
    {
        n ++;
        a[n] = b[i];
        solve_query();
    }
        }

}

int main()
{
    ///freopen("test.txt", "r", stdin);
    solve();
    return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:73:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   73 |     for (int i = 1; i <= m; i ++)
      |     ^~~
Main.cpp:76:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   76 |         bool sorted = true;
      |         ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Correct 3 ms 212 KB Output is correct
3 Correct 4 ms 212 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 3 ms 212 KB Output is correct
6 Correct 4 ms 212 KB Output is correct
7 Correct 3 ms 212 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 345 ms 1740 KB Output is correct
10 Correct 391 ms 1764 KB Output is correct
11 Correct 277 ms 1864 KB Output is correct
12 Correct 404 ms 1864 KB Output is correct
13 Correct 268 ms 1960 KB Output is correct
14 Correct 332 ms 1860 KB Output is correct
15 Correct 312 ms 1944 KB Output is correct
16 Correct 305 ms 1960 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 2804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 2804 KB Output isn't correct
2 Halted 0 ms 0 KB -