oj.uz

Submission #1063614

# Submission time Handle Problem Language Result Execution time Memory
1063614 2024-08-17T21:19:12 Z TimDee Seesaw (JOI22_seesaw) C++17
67 / 100
 711 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define forn(i,n) for(int i=0; i<n; ++i)
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()

#define double long double
const double one = 1;
const int N=1005;
double med[N][N];

int a[N];

double bad(int n) {

	vector<pair<double,int>> v;
	forn(i,n) {
		int s=0;
		for(int j=i; j<n; ++j) {
			s+=a[j];
			double z = 1.0*s/(j-i+1);
			v.pb({z,j-i});
		}
	}
	sort(all(v));
	vector<int> cnt(n);
	int tot=0;
	int r=0;
	double ans=a[n-1]-a[0];
	forn(i,v.size()) {
		while (r<v.size() && tot<n) {
			tot+=!cnt[v[r].s];
			++cnt[v[r].s];
			++r;
		}
		if (tot==n) ans=min(ans,v[r-1].f - v[i].f);
		--cnt[v[i].s];
		tot-=!cnt[v[i].s];
	}
	return ans;
	cout<<fixed<<setprecision(10)<<ans<<'\n';

}

double good(int n) {

	int sum=0; forn(i,n) sum+=a[i];
	double ans = a[n-1]-a[0];
	const double z = one*sum/n;
	forn(mask,1<<(n-1)) {
		int l=0, r=n-1;
		double lx=z, rx=z;
		int s=sum;
		forn(i,n-1) {
			if ((mask>>i)&1) {
				s-=a[l++];
			} else {
				s-=a[r--];
			}
			lx = min(lx,one*s/(r-l+1));
			rx = max(rx,one*s/(r-l+1));
		}
		//cout<<"??? "<<mask<<"  "<<lx<<' '<<rx<<'\n';
		ans=min(ans,rx-lx);
	}
	return ans;

}

void solve() {
	
	int n; cin>>n;
	forn(i,n) cin>>a[i];
	cout<<fixed<<setprecision(10)<<bad(n)<<'\n';

}

mt19937 rng(1337);

int rand(int a, int b) {
	return a + rng()%(b-a+1);
}
void gen() {
	int n=rand(2,6);
	a[0]=rand(1,10);
	for(int i=1; i<n; ++i) a[i]=rand(a[i-1]+1,10+i);
	auto f = good(n);
	auto s = bad(n);
	const double eps = 1e-9;
	if (abs(f-s)>eps) {
		cout<<"WA\n";
		cout<<n<<'\n';
		forn(i,n) cout<<a[i]<<' '; cout<<'\n';
		cout<<fixed<<setprecision(10)<<"AC: "<<f<<" , WA: "<<s<<'\n';
		exit(0);
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//while (1) gen();
	solve();
}

Compilation message

seesaw.cpp: In function 'long double bad(long long int)':
seesaw.cpp:5:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long double, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define forn(i,n) for(int i=0; i<n; ++i)
......
   35 |  forn(i,v.size()) {
      |       ~~~~~~~~~~                 
seesaw.cpp:35:2: note: in expansion of macro 'forn'
   35 |  forn(i,v.size()) {
      |  ^~~~
seesaw.cpp:36:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long double, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   while (r<v.size() && tot<n) {
      |          ~^~~~~~~~~
seesaw.cpp: In function 'void gen()':
seesaw.cpp:5:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    5 | #define forn(i,n) for(int i=0; i<n; ++i)
      |                   ^~~
seesaw.cpp:98:3: note: in expansion of macro 'forn'
   98 |   forn(i,n) cout<<a[i]<<' '; cout<<'\n';
      |   ^~~~
seesaw.cpp:98:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   98 |   forn(i,n) cout<<a[i]<<' '; cout<<'\n';
      |                              ^~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
33.0 / 33.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 336 ms 66864 KB Output is correct
9 Correct 332 ms 66728 KB Output is correct
10 Correct 327 ms 67752 KB Output is correct
11 Correct 327 ms 66988 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 336 ms 66864 KB Output is correct
9 Correct 332 ms 66728 KB Output is correct
10 Correct 327 ms 67752 KB Output is correct
11 Correct 327 ms 66988 KB Output is correct
12 Runtime error 711 ms 1048576 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -