Submission #348264

#	Time	Username	Problem	Language	Result	Execution time	Memory
348264		MrDomino	Safety (NOI18_safety)	C++14	33 / 100	2084 ms	1672 KiB

safety

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int ll

multiset<int> local_minimum(multiset<int> s, int h) {
  assert((int) s.size() % 2 == 0);
  multiset<int> s2;
  int slope = -(int) s.size() / 2;
  for (auto &x : s) {
    if (slope < 0) {
      s2.insert(x - h);
    }
    if (slope >= 0) {
      s2.insert(x + h);
    }
    slope++;
  }
  return s2;
}

/**
void print(multiset<int> s) {
  cout << " : ";
  for (auto &x : s) {
    cout << x << " ";
  }
  cout << "\n";
 // cout << ", ";
}**/

vector<pair<int, int>> get(multiset<int> s, int a, int b) {
  vector<int> xs;
  for (auto &it : s) {
    xs.push_back(it);
  }
  int n = (int) xs.size();
  vector<pair<int, int>> ret;
  ret.push_back({a, b});
  for (int i = n - 1; i >= 0; i--) {
    /// (a - 1) * x + b2 = a * x + b
    /// a * x - x + b2 = a * x + b
    /// b2 - x = b
    /// b2 = x + b
    b += xs[i];
    a--;
    ret.push_back({a, b});
  }


  reverse(ret.begin(), ret.end());
  return ret;
}

const int c = 100;

void print(multiset<int> s, int b) {
  for (auto &x : s) {
    cout << x << " ";
  }
  cout << " :\n";
  int a = (int) s.size() / 2;

  /**

bug:
  3 1
7 7 7


  s.clear();
  s.insert(2);
  s.insert(8);
  s.insert(8);
  s.insert(8);
  b = -24;
  a = 4;**/

  vector<pair<int, int>> v = get(s, a, b);
  int last = -c;
  auto ko = s.begin();
  s.insert(+c);
  for (auto &it : v) {
    cout << "for x = " << last << "..." << *ko << " : ";
    last = *ko;
    ko++;
    cout << "f(x) = x * " << it.first << " + " << it.second << "\n";
  }
  cout << "\n";
}


int solve(multiset<int> s, int b) {
  int a = (int) s.size() / 2;
  vector<pair<int, int>> v = get(s, a, b);
  for (auto &it : v) {
    if (it.first == 0) {
      return it.second;
    }
  }
  assert(0);
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  //freopen ("input", "r", stdin);

  multiset<int> s;
  int n, h, x, b = 0;
  cin >> n >> h >> x;
  s.insert(x);
  s.insert(x);
  b = -x;

  for (int i = 2; i <= n; i++) {
    s = local_minimum(s, h);
    cin >> x;
    b -= (i - 1) * h; /// I have no clue why this happens lol

    /**if (i == n) {
      cout << "lol\n";
      print(s, b);
      return 0;
    }**/

    s.insert(x);
    s.insert(x);
    auto it = s.end();
    it--;
    b -= x;
//    print(s, b);
//    cout << "\n";
  //  return 0;
  //  cout << " => " << b << "\n";
  //  print(s, b);
  //  return 0;
  }

  int a = (int) s.size() / 2;

  /**

bug:
  3 1
7 7 7


  s.clear();
  s.insert(2);
  s.insert(8);
  s.insert(8);
  s.insert(8);
  b = -24;
  a = 4;**/

  vector<pair<int, int>> v = get(s, a, b);
  for (auto &it : v)
 {

   if (it.first == 0) {
    cout << it.second << "\n";
   }
 } // print(s, b);

}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 0 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 22
• Subtask 9: 0 / 29