oj.uz

Submission #1081777

# Submission time Handle Problem Language Result Execution time Memory
1081777 2024-08-30T10:30:20 Z vjudge1 Measures (CEOI22_measures) C++17
59 / 100
 372 ms 5712 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mod 998244353
#define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<pair<pair<int,int>,int>,null_type,less<pair<pair<int,int>,int>>,rb_tree_tag,tree_order_statistics_node_update>;
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m,d;
    cin>>n>>m>>d;
    if(n){
        d*=2;
        vector<int>v(n);
        for(auto &i:v){cin>>i;i*=2;}
        while(m--){
            int x;
            cin>>x;
            x*=2;
            v.push_back(x);
            sort(v.begin(),v.end());
            int l=0,r=1000000000,mid,f;
            r*=r;
            while(l<=r){
                mid=(l+r)/2;
                vector<int>vv=v;
                vv[0]-=mid;
                bool bl=1;
                for(int i=1;i<vv.size();i++){
                    vv[i]=max(vv[i]-mid,vv[i-1]+d);
                    if(abs(vv[i]-v[i])>mid)bl=0;
                }
                if(bl){
                    r=mid-1;
                    f=mid;
                }else l=mid+1;
            }
            cout<<f/2;
            if(f&1)cout<<".5";
            cout<<' ';
        }

    }else{
        d*=2;
        int ls=INT_MIN;
        int ans=0;
        while(m--){
            int x;
            cin>>x;
            x*=2;
            int ogx=x;
            // cout<<max(ls+d,x-ans)<<' ';
            x=max(ls+d,x-ans);
            int g=abs(x-ogx)-ans;
            g=max(g,0ll);
            ls=x-g/2;
            ans+=g/2;
            cout<<ans/2;
            if(ans&1)cout<<".5";
            cout<<' ';
        }
    }
}
/*
1
13
7 10 13 |4 |5 10| 8| 3 6 5 |7 10| 2


*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:31:30: 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]
   31 |                 for(int i=1;i<vv.size();i++){
      |                             ~^~~~~~~~~~
Main.cpp:41:17: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |             if(f&1)cout<<".5";
      |                ~^~

Subtask #1
10.0 / 10.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 356 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 326 ms 5464 KB Output is correct
10 Correct 359 ms 5464 KB Output is correct
11 Correct 266 ms 5464 KB Output is correct
12 Correct 372 ms 5712 KB Output is correct
13 Correct 272 ms 4956 KB Output is correct
14 Correct 314 ms 5344 KB Output is correct
15 Correct 308 ms 4700 KB Output is correct
16 Correct 268 ms 5340 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3324 KB Output is correct
2 Correct 28 ms 5200 KB Output is correct
3 Correct 27 ms 5256 KB Output is correct
4 Correct 22 ms 3156 KB Output is correct
5 Correct 25 ms 4444 KB Output is correct
6 Correct 26 ms 3412 KB Output is correct
7 Correct 29 ms 4436 KB Output is correct
8 Correct 24 ms 3232 KB Output is correct
9 Correct 34 ms 3272 KB Output is correct
10 Correct 29 ms 5456 KB Output is correct
11 Correct 30 ms 3920 KB Output is correct
12 Correct 28 ms 4748 KB Output is correct
13 Correct 29 ms 3156 KB Output is correct
14 Correct 38 ms 4948 KB Output is correct
15 Correct 29 ms 4700 KB Output is correct
16 Correct 23 ms 2652 KB Output is correct
17 Correct 35 ms 4432 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3324 KB Output is correct
2 Correct 28 ms 5200 KB Output is correct
3 Correct 27 ms 5256 KB Output is correct
4 Correct 22 ms 3156 KB Output is correct
5 Correct 25 ms 4444 KB Output is correct
6 Correct 26 ms 3412 KB Output is correct
7 Correct 29 ms 4436 KB Output is correct
8 Correct 24 ms 3232 KB Output is correct
9 Correct 34 ms 3272 KB Output is correct
10 Correct 29 ms 5456 KB Output is correct
11 Correct 30 ms 3920 KB Output is correct
12 Correct 28 ms 4748 KB Output is correct
13 Correct 29 ms 3156 KB Output is correct
14 Correct 38 ms 4948 KB Output is correct
15 Correct 29 ms 4700 KB Output is correct
16 Correct 23 ms 2652 KB Output is correct
17 Correct 35 ms 4432 KB Output is correct
18 Incorrect 27 ms 4436 KB Output isn't correct
19 Halted 0 ms 0 KB -