oj.uz

Submission #1063621

# Submission time Handle Problem Language Result Execution time Memory
1063621 2024-08-17T21:23:49 Z TimDee Seesaw (JOI22_seesaw) C++17
67 / 100
 738 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 1 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 1 ms 348 KB Output is correct
4 Correct 1 ms 856 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 1 ms 348 KB Output is correct
4 Correct 1 ms 856 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 339 ms 66216 KB Output is correct
9 Correct 342 ms 66068 KB Output is correct
10 Correct 340 ms 66196 KB Output is correct
11 Correct 341 ms 66116 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 1 ms 348 KB Output is correct
4 Correct 1 ms 856 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 339 ms 66216 KB Output is correct
9 Correct 342 ms 66068 KB Output is correct
10 Correct 340 ms 66196 KB Output is correct
11 Correct 341 ms 66116 KB Output is correct
12 Runtime error 738 ms 1048576 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -