oj.uz

Submission #825205

# Submission time Handle Problem Language Result Execution time Memory
825205 2023-08-14T15:38:52 Z Um_nik Seesaw (JOI22_seesaw) C++17
100 / 100
 75 ms 12388 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#include <climits>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}

#define mp make_pair
#define all(x) (x).begin(),(x).end()

clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

ll floor_div(ll x, ll y) {
	assert(y != 0);
	if (y < 0) {
		y = -y;
		x = -x;
	}
	if (x >= 0) return x / y;
	return (x + 1) / y - 1;
}
ll ceil_div(ll x, ll y) {
	assert(y != 0);
	if (y < 0) {
		y = -y;
		x = -x;
	}
	if (x <= 0) return x / y;
	return (x - 1) / y + 1;
}

const double eps = 1e-10;
bool eq(double x, double y) {
	return abs(x - y) < eps;
}

const int N = 200400;
int n;
ll a[N];
ll pref[N];
int cnt[N];
pair<double, int> ev[2 * N];
int bad;

void addOne(int x) {
	if (cnt[x] == 0) bad--;
	cnt[x]++;
}
void remOne(int x) {
	cnt[x]--;
	if (cnt[x] == 0) bad++;
}

int main() {
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%lld", &a[i]);
	for (int i = 0; i < n; i++)
		pref[i + 1] = pref[i] + a[i];
	double M = (double)pref[n] / n;
	ev[0] = mp(M, 0);
	for (int k = 1; k < n; k++) {
		int l = 0, r = n - k;
		while(r - l > 1) {
			int x = (l + r) / 2;
			if (pref[x + k] - pref[x] < M * k)
				l = x;
			else
				r = x;
		}
		ev[2 * k - 1] = mp((double)(pref[l + k] - pref[l]) / k, k);
		ev[2 * k] = mp((double)(pref[r + k] - pref[r]) / k, k);
	}
	bad = n;
	double ans = a[n - 1] - a[0];
	n = 2 * n - 1;
	sort(ev, ev + n);
	int r = 0;
	for (int l = 0; l < n; l++) {
		while(r < n && (bad > 0 || eq(ev[r].first, ev[r - 1].first))) {
			addOne(ev[r++].second);
		}
		if (bad > 0) break;
		ans = min(ans, ev[r - 1].first - ev[l].first);
		remOne(ev[l].second);
	}
	printf("%.15lf\n", ans);

	return 0;
}

Compilation message

seesaw.cpp: In function 'int main()':
seesaw.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
seesaw.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   scanf("%lld", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 75 ms 12388 KB Output is correct
13 Correct 75 ms 12332 KB Output is correct
14 Correct 75 ms 12384 KB Output is correct
15 Correct 75 ms 12308 KB Output is correct
16 Correct 74 ms 12320 KB Output is correct