Submission #1291990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291990		HoriaHaivas	Measures (CEOI22_measures)	C++20	0 / 100	1591 ms	568 KiB

Main

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

double dp[200105];
double coord[200105];
int n,d;

bool ok(double x)
{
     int i;
     for (i=1;i<=n;i++)
     {
          if (i==1)
              dp[i]=coord[i]-x;
          else
          {
              if (coord[i]-dp[i-1]>=d)
                  dp[i]=coord[i]-(coord[i]-dp[i-1]-d);
              else
              {
                  if (coord[i]+x<dp[i-1]+d)
                      return false;
                  else
                      dp[i]=dp[i-1]+d;
              }
          }
     }
     return true;
}

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int m,i,j,pas,x;
    double r;
    cin >> n >> m >> d;
    for (i=1;i<=n;i++)
    {
         cin >> coord[i];
    }
    sort(coord+1,coord+1+n);
    for (i=1;i<=m;i++)
    {
         cin >> x;
         n++;
         coord[n]=x;
         sort(coord+1,coord+1+n);///imi e lene sa fac liniar
         if (n==1)
         {
             cout << "0 ";
             continue;
         }
         r=0;
         pas=(1LL<<60);
         while (pas)
         {
             if (!ok(r+pas))
                 r+=pas;
             pas=pas/2;
         }

         if (ok(r+0.5))
             cout << r+0.5 << " ";
         else
             cout << r+1 << " ";
    }
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41