Submission #724709

#TimeUsernameProblemLanguageResultExecution timeMemory
724709406Sparklers (JOI17_sparklers)C++17
0 / 100
1 ms512 KiB
#include "bits/stdc++.h" #define int long long #define dq deque<int> using namespace std; const long long INF = 1ll << 35; const int N = 1e5 + 5; int n, k, t, x[N]; dq L, R; void ps(dq &v) { v.push_front(0); for (int i = 1; i < v.size(); i++) v[i] += v[i - 1]; } array<int, 3> find(const dq &v) { int mn = v[0]; for (int i = 1; i < v.size(); i++) { int u = v[1]; mn = min(mn, u); if (u >= v[0]) return {u, mn, 1}; } return {0, 0, 0}; } bool solve(array<dq, 2> v, int d = 0) { array<int, 3> A[2]; A[0] = find(v[0]); A[1] = find(v[1]); while (v[0].size() > 1 || v[1].size() > 1) { //assert(v[0].size() && v[1].size()); //cout << v[0].size() << ' ' << v[1].size() << endl; bool flag = false; for (int k = 0; k < 2; k++) if (A[k][2]) { if (v[k ^ 1][0] + A[k][1] >= 0) { v[k].pop_front(); while (v[k][0] != A[k][0]) v[k].pop_front(); A[k] = find(v[k]); flag = true; } } if (flag) continue; else if (A[0][2] && A[1][2]) return false; if (!A[0][2] && !A[1][2]) { if (v[0].size() == 1 && v[1].size() == 1) return false; assert(d == 0); //cout << "REVERSE SOLVE " << endl; for (int k = 0; k < 2; k++) reverse(v[k].begin(), v[k].end()); return solve(v, d + 1); } else return false; } return true; } bool check(int O) { int s = O * 2 * t; dq l = L, r = R; for (auto &u: l) u = s - u; for (auto &u: r) u = s - u; ps(l), ps(r); array<dq, 2> v = {l, r}; /* for (auto u: l) cout << u << ' '; cout << endl; for (auto u: r) cout << u << ' '; cout << endl; */ return solve(v); } signed main() { cin >> n >> k >> t; k--; for (int i = 0; i < n; i++) cin >> x[i]; for (int i = 0; i < k; i++) L.push_back(x[i + 1] - x[i]); reverse(L.begin(), L.end()); for (int i = k + 1; i < n; i++) R.push_back(x[i] - x[i - 1]); int l = -1, r = INF; while (r - l > 1) { int m = l + r >> 1; if (check(m)) r = m; else l = m; } cout << r << '\n'; return 0; } //

Compilation message (stderr)

sparklers.cpp: In function 'void ps(std::deque<long long int>&)':
sparklers.cpp:12:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for (int i = 1; i < v.size(); i++) v[i] += v[i - 1];
      |                  ~~^~~~~~~~~~
sparklers.cpp: In function 'std::array<long long int, 3> find(const std::deque<long long int>&)':
sparklers.cpp:17:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for (int i = 1; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
sparklers.cpp: In function 'int main()':
sparklers.cpp:91:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |   int m = l + r >> 1;
      |           ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...