oj.uz

Submission #883125

# Submission time Handle Problem Language Result Execution time Memory
883125 2023-12-04T15:11:33 Z fanwen Measures (CEOI22_measures) C++17
24 / 100
 279 ms 4700 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define file(name)                  \
    if(fopen(name".inp", "r"))      \
        freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \

const int MAX = 2e5 + 5;

int n, m, D, a[MAX];

namespace sub1 {

	long long calc(const vector <int> &a) {
		auto check = [&] (long long val) -> bool {
			long long last = 1e18;
			for (int i = (int) a.size() - 1; i >= 0; --i) {
				if(last + val < a[i]) return false;
				last = min(last - D, a[i] + val - D);
			}
			return true;
		};

		long long l = -1, r = 1e18;
		while(r - l > 1) {
			long long mid = l + r >> 1;
			if(check(mid)) r = mid;
			else l = mid;
		}
		return r;
	}
	void solve() {
		D <<= 1;
		for (int i = 1; i <= n; ++i) a[i] <<= 1;
		vector <int> b(a + 1, a + n + 1);

		for (int i = 1; i <= m; ++i) {
			int x; cin >> x;
			b.push_back(x << 1);
			sort(b.begin(), b.end());
			long long ans = calc(b);
			cout << ans / 2;
			if(ans & 1) cout <<  ".5";
			cout << " ";
		}
		exit(0);
	}
}

void you_make_it(void) {
    cin >> n >> m >> D;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    if(n > 0) sub1::solve();
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("CEOI22_measures");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message

Main.cpp: In function 'long long int sub1::calc(const std::vector<int>&)':
Main.cpp:30:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |    long long mid = l + r >> 1;
      |                    ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:66:5: note: in expansion of macro 'file'
   66 |     file("CEOI22_measures");
      |     ^~~~
Main.cpp:10:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:66:5: note: in expansion of macro 'file'
   66 |     file("CEOI22_measures");
      |     ^~~~

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 2 ms 476 KB Output is correct
4 Correct 3 ms 516 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 3 ms 348 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 2 ms 476 KB Output is correct
4 Correct 3 ms 516 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 223 ms 4504 KB Output is correct
10 Correct 271 ms 4524 KB Output is correct
11 Correct 173 ms 4688 KB Output is correct
12 Correct 279 ms 4700 KB Output is correct
13 Correct 172 ms 4184 KB Output is correct
14 Correct 206 ms 4700 KB Output is correct
15 Correct 220 ms 3928 KB Output is correct
16 Correct 174 ms 4700 KB Output is correct

Subtask #3
0 / 35.0

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

Subtask #4
0 / 41.0

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