답안 #901580

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
901580 2024-01-09T15:39:37 Z ByeWorld Gap (APIO16_gap) C++14
0 / 100
20 ms 3108 KB
#include "gap.h"
#include <bits/stdc++.h>
#define bupol __builtin_popcount
//#define int long long 
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 1e5+5;
const int MAXK = 205;
const int LOG = 20;
const int MOD = 1e9+7;
const int SQRT = 520;
const ll INF = 1e18+10;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> ipii;

ll mn, mx;
ll x, y;
int n;
set<ll> s; ll ans = INF;

void sol(ll l, ll r){ // cari semua di range l-r
	//cout << l << ' '<< r << " p\n";
	if(l > r || r-l+1 <= ans) return;
	MinMax(l, r, &mn, &mx);
	if(mn > mx){ // pasti berurutan
		ans = max(ans, mn-mx);
		s.insert(mn); s.insert(mx);
		return;
	}
	//if(mn==-1 || mx==-1) return; // gk ada lagi di range ini
	if(s.find(mn)!=s.end() && s.find(mx)!=s.end()) return;
	s.insert(mn); s.insert(mx);

	int tmn = mn, tmx = mx;
	tmn++; tmx--;
	sol(tmn, ((tmn+tmx)>>1) ); 
	//cout << ((tmn+tmx)>>1)+1 << ' '<< tmx << " oo\n";
	sol(((tmn+tmx)>>1)+1, tmx);
}

long long findGap(int T, int N)
{
	n = N;
	sol(0, INF);
	//for(auto in : s) cout << in << " xx\n";
	auto it = s.begin(), it2 = s.begin(); it2++;
	while(it2 != s.end()){
		if((*it)!=-1) ans = max(ans, (*it2)-(*it));
		it++; it2++;
	}
	return ans;
}
	// for(int i=1; i<=(n+1)/2; i++){
	// 	MinMax(x, y, &mn, &mx);
	// 	a[i] = mn; a[n-i+1] = mx;
	// 	//cout << mn << ' '<< mx << " p\n";
	// 	x = mn+1; y = mx-1;
	// }
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Incorrect 1 ms 2392 KB Output isn't correct
3 Incorrect 0 ms 2392 KB Output isn't correct
4 Incorrect 0 ms 2392 KB Output isn't correct
5 Incorrect 1 ms 2392 KB Output isn't correct
6 Incorrect 0 ms 2392 KB Output isn't correct
7 Incorrect 1 ms 2392 KB Output isn't correct
8 Incorrect 0 ms 2392 KB Output isn't correct
9 Incorrect 1 ms 2392 KB Output isn't correct
10 Incorrect 1 ms 2392 KB Output isn't correct
11 Incorrect 1 ms 2392 KB Output isn't correct
12 Incorrect 1 ms 2392 KB Output isn't correct
13 Incorrect 1 ms 2392 KB Output isn't correct
14 Incorrect 1 ms 2392 KB Output isn't correct
15 Incorrect 1 ms 2392 KB Output isn't correct
16 Incorrect 4 ms 2580 KB Output isn't correct
17 Incorrect 4 ms 2584 KB Output isn't correct
18 Incorrect 4 ms 2392 KB Output isn't correct
19 Incorrect 4 ms 2592 KB Output isn't correct
20 Incorrect 3 ms 2568 KB Output isn't correct
21 Incorrect 14 ms 3020 KB Output isn't correct
22 Incorrect 14 ms 3108 KB Output isn't correct
23 Incorrect 15 ms 2856 KB Output isn't correct
24 Incorrect 14 ms 3096 KB Output isn't correct
25 Incorrect 12 ms 2848 KB Output isn't correct
26 Incorrect 14 ms 2852 KB Output isn't correct
27 Incorrect 14 ms 2856 KB Output isn't correct
28 Incorrect 14 ms 2852 KB Output isn't correct
29 Incorrect 14 ms 2852 KB Output isn't correct
30 Incorrect 10 ms 2836 KB Output isn't correct
31 Incorrect 0 ms 2392 KB Output isn't correct
32 Incorrect 0 ms 2392 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2388 KB Output isn't correct
2 Incorrect 1 ms 2392 KB Output isn't correct
3 Incorrect 0 ms 2392 KB Output isn't correct
4 Incorrect 1 ms 2392 KB Output isn't correct
5 Incorrect 0 ms 2392 KB Output isn't correct
6 Incorrect 0 ms 2392 KB Output isn't correct
7 Incorrect 0 ms 2392 KB Output isn't correct
8 Incorrect 0 ms 2392 KB Output isn't correct
9 Incorrect 0 ms 2392 KB Output isn't correct
10 Incorrect 1 ms 2392 KB Output isn't correct
11 Incorrect 1 ms 2392 KB Output isn't correct
12 Incorrect 1 ms 2392 KB Output isn't correct
13 Incorrect 1 ms 2392 KB Output isn't correct
14 Incorrect 1 ms 2392 KB Output isn't correct
15 Incorrect 1 ms 2392 KB Output isn't correct
16 Incorrect 4 ms 2580 KB Output isn't correct
17 Incorrect 4 ms 2588 KB Output isn't correct
18 Incorrect 4 ms 2744 KB Output isn't correct
19 Incorrect 4 ms 2824 KB Output isn't correct
20 Incorrect 3 ms 2644 KB Output isn't correct
21 Incorrect 14 ms 2848 KB Output isn't correct
22 Incorrect 14 ms 2852 KB Output isn't correct
23 Incorrect 15 ms 2856 KB Output isn't correct
24 Incorrect 14 ms 2852 KB Output isn't correct
25 Incorrect 12 ms 2792 KB Output isn't correct
26 Incorrect 14 ms 2852 KB Output isn't correct
27 Incorrect 14 ms 2852 KB Output isn't correct
28 Incorrect 20 ms 2832 KB Output isn't correct
29 Incorrect 15 ms 2852 KB Output isn't correct
30 Incorrect 9 ms 2848 KB Output isn't correct
31 Incorrect 0 ms 2392 KB Output isn't correct
32 Incorrect 0 ms 2392 KB Output isn't correct