제출 #825205

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
825205		Um_nik	Seesaw (JOI22_seesaw)	C++17	100 / 100	75 ms	12388 KiB

seesaw

//#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 1
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 33 / 33