답안 #916055

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916055	2024-01-25T08:14:40 Z	GrindMachine	Gap (APIO16_gap)	C++17	0 / 100	2000 ms	15260 KB

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

read some solutions a long time ago, slightly remember some ideas
may have still solved it if not for those ideas

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
const int B = 1e5 + 5;

#include "gap.h"

ll go(ll l, ll r){
	if(l >= r) return 0;

	// split into B segs
	ll len = r-l+1;
	ll cnt1 = B;
	ll cnt2 = len%B;
	cnt1 -= cnt2;

	vector<pll> segs;
	ll ptr = l;

	rep1(i,cnt1){
		if(len >= B){
			segs.pb({ptr,ptr+len/B-1});
		}
		ptr += len/B;
	}

	rep1(i,cnt2){
		segs.pb({ptr,ptr+ceil2(len,B)-1});
		ptr += ceil2(len,B);
	}

	// cout << "l = " << l << endl;
	// cout << "r = " << r << endl;
	// for(auto [lx,rx] : segs){
	// 	cout << lx << " " << rx << endl;
	// }

	assert(ptr == r+1);

	vector<pll> seg_vals;
	ll ans = 0;

	rep(i,sz(segs)){
		ll mn,mx;
		auto [lx,rx] = segs[i];
		MinMax(lx,rx,&mn,&mx);
		seg_vals.pb({mn,mx});
		if(mn != -1){
			amax(ans,go(lx,rx));
		}
	}

	ll last_active = -1;

	for(auto [mn,mx] : seg_vals){
		if(mn != -1){
			if(last_active != -1){
				amax(ans,mn-last_active);
			}
			last_active = mx;
		}
	}

	return ans;
}

long long findGap(int T, int n)
{
	return go(0,inf2);
}

Subtask #1
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	21 ms	11220 KB	Output isn't correct
2	Incorrect	147 ms	13764 KB	Output isn't correct
3	Incorrect	147 ms	13216 KB	Output isn't correct
4	Incorrect	149 ms	13856 KB	Output isn't correct
5	Incorrect	23 ms	10448 KB	Output isn't correct
6	Incorrect	1287 ms	13596 KB	Output isn't correct
7	Incorrect	1316 ms	13508 KB	Output isn't correct
8	Incorrect	1386 ms	14000 KB	Output isn't correct
9	Incorrect	1289 ms	15200 KB	Output isn't correct
10	Incorrect	24 ms	10192 KB	Output isn't correct
11	Execution timed out	3034 ms	12880 KB	Time limit exceeded
12	Execution timed out	3045 ms	14796 KB	Time limit exceeded
13	Execution timed out	3012 ms	12700 KB	Time limit exceeded
14	Execution timed out	3016 ms	13080 KB	Time limit exceeded
15	Incorrect	507 ms	11820 KB	Output isn't correct
16	Execution timed out	3040 ms	12844 KB	Time limit exceeded
17	Execution timed out	3046 ms	12520 KB	Time limit exceeded
18	Execution timed out	3024 ms	12472 KB	Time limit exceeded
19	Execution timed out	3056 ms	12664 KB	Time limit exceeded
20	Incorrect	51 ms	10368 KB	Output isn't correct
21	Execution timed out	3066 ms	12808 KB	Time limit exceeded
22	Execution timed out	3060 ms	12916 KB	Time limit exceeded
23	Execution timed out	3047 ms	12784 KB	Time limit exceeded
24	Execution timed out	3019 ms	12916 KB	Time limit exceeded
25	Execution timed out	3019 ms	12372 KB	Time limit exceeded
26	Execution timed out	3048 ms	12900 KB	Time limit exceeded
27	Execution timed out	3006 ms	13508 KB	Time limit exceeded
28	Execution timed out	3037 ms	12720 KB	Time limit exceeded
29	Execution timed out	3030 ms	12972 KB	Time limit exceeded
30	Incorrect	92 ms	10632 KB	Output isn't correct
31	Incorrect	354 ms	13952 KB	Output isn't correct
32	Incorrect	351 ms	13960 KB	Output isn't correct

Subtask #2
0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	20 ms	12844 KB	Partially correct
2	Partially correct	147 ms	13224 KB	Partially correct
3	Partially correct	142 ms	13628 KB	Partially correct
4	Partially correct	152 ms	13308 KB	Partially correct
5	Partially correct	19 ms	10192 KB	Partially correct
6	Partially correct	1308 ms	14444 KB	Partially correct
7	Partially correct	1357 ms	14752 KB	Partially correct
8	Partially correct	1285 ms	13732 KB	Partially correct
9	Partially correct	1331 ms	15260 KB	Partially correct
10	Partially correct	23 ms	10192 KB	Partially correct
11	Execution timed out	3018 ms	15032 KB	Time limit exceeded
12	Execution timed out	3096 ms	13532 KB	Time limit exceeded
13	Execution timed out	3009 ms	14968 KB	Time limit exceeded
14	Execution timed out	3025 ms	12632 KB	Time limit exceeded
15	Partially correct	490 ms	11852 KB	Partially correct
16	Execution timed out	3041 ms	12420 KB	Time limit exceeded
17	Execution timed out	3011 ms	12644 KB	Time limit exceeded
18	Execution timed out	3047 ms	12616 KB	Time limit exceeded
19	Execution timed out	3042 ms	12548 KB	Time limit exceeded
20	Partially correct	58 ms	10236 KB	Partially correct
21	Execution timed out	3065 ms	12704 KB	Time limit exceeded
22	Execution timed out	3054 ms	12608 KB	Time limit exceeded
23	Execution timed out	3041 ms	13164 KB	Time limit exceeded
24	Execution timed out	3014 ms	12732 KB	Time limit exceeded
25	Execution timed out	3014 ms	12056 KB	Time limit exceeded
26	Execution timed out	3090 ms	12864 KB	Time limit exceeded
27	Execution timed out	3029 ms	12956 KB	Time limit exceeded
28	Execution timed out	3024 ms	13000 KB	Time limit exceeded
29	Execution timed out	3036 ms	13672 KB	Time limit exceeded
30	Partially correct	88 ms	10636 KB	Partially correct
31	Partially correct	363 ms	13912 KB	Partially correct
32	Partially correct	347 ms	14160 KB	Partially correct

답안 #916055

Compilation message

Subtask #1 0 / 30.0

Subtask #2 0 / 70.0

Subtask #1
0 / 30.0

Subtask #2
0 / 70.0