답안 #916056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916056	2024-01-25T08:15:31 Z	GrindMachine	Gap (APIO16_gap)	C++17	0 / 100	2000 ms	3260 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 = 315;

#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	1 ms	344 KB	Output isn't correct
2	Incorrect	2 ms	2392 KB	Output isn't correct
3	Incorrect	2 ms	2392 KB	Output isn't correct
4	Incorrect	3 ms	2392 KB	Output isn't correct
5	Incorrect	2 ms	2392 KB	Output isn't correct
6	Incorrect	12 ms	2392 KB	Output isn't correct
7	Incorrect	16 ms	2392 KB	Output isn't correct
8	Incorrect	12 ms	2392 KB	Output isn't correct
9	Incorrect	11 ms	2392 KB	Output isn't correct
10	Incorrect	1 ms	2392 KB	Output isn't correct
11	Incorrect	210 ms	2640 KB	Output isn't correct
12	Incorrect	205 ms	2604 KB	Output isn't correct
13	Incorrect	204 ms	2616 KB	Output isn't correct
14	Incorrect	207 ms	2592 KB	Output isn't correct
15	Incorrect	82 ms	2580 KB	Output isn't correct
16	Execution timed out	3047 ms	2700 KB	Time limit exceeded
17	Execution timed out	3060 ms	2692 KB	Time limit exceeded
18	Execution timed out	3031 ms	2688 KB	Time limit exceeded
19	Execution timed out	3035 ms	2692 KB	Time limit exceeded
20	Incorrect	14 ms	2572 KB	Output isn't correct
21	Execution timed out	3026 ms	2856 KB	Time limit exceeded
22	Execution timed out	3100 ms	2964 KB	Time limit exceeded
23	Execution timed out	3047 ms	3124 KB	Time limit exceeded
24	Execution timed out	3021 ms	2964 KB	Time limit exceeded
25	Execution timed out	3023 ms	2940 KB	Time limit exceeded
26	Execution timed out	3034 ms	2852 KB	Time limit exceeded
27	Execution timed out	3034 ms	2956 KB	Time limit exceeded
28	Execution timed out	3059 ms	3260 KB	Time limit exceeded
29	Execution timed out	3038 ms	2940 KB	Time limit exceeded
30	Incorrect	53 ms	3196 KB	Output isn't correct
31	Incorrect	7 ms	2392 KB	Output isn't correct
32	Incorrect	4 ms	2392 KB	Output isn't correct

Subtask #2
0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	1 ms	2392 KB	Partially correct
2	Partially correct	2 ms	2392 KB	Partially correct
3	Partially correct	2 ms	2392 KB	Partially correct
4	Partially correct	2 ms	2392 KB	Partially correct
5	Partially correct	1 ms	2640 KB	Partially correct
6	Partially correct	11 ms	2392 KB	Partially correct
7	Partially correct	19 ms	2404 KB	Partially correct
8	Partially correct	11 ms	2392 KB	Partially correct
9	Partially correct	11 ms	2392 KB	Partially correct
10	Partially correct	1 ms	2392 KB	Partially correct
11	Partially correct	205 ms	2616 KB	Partially correct
12	Partially correct	222 ms	2600 KB	Partially correct
13	Partially correct	206 ms	2392 KB	Partially correct
14	Partially correct	226 ms	2640 KB	Partially correct
15	Partially correct	81 ms	2580 KB	Partially correct
16	Execution timed out	3041 ms	2688 KB	Time limit exceeded
17	Execution timed out	3016 ms	2688 KB	Time limit exceeded
18	Execution timed out	3041 ms	2844 KB	Time limit exceeded
19	Execution timed out	3046 ms	2688 KB	Time limit exceeded
20	Partially correct	15 ms	2532 KB	Partially correct
21	Execution timed out	3043 ms	2964 KB	Time limit exceeded
22	Execution timed out	3025 ms	2960 KB	Time limit exceeded
23	Execution timed out	3013 ms	3020 KB	Time limit exceeded
24	Execution timed out	3004 ms	2960 KB	Time limit exceeded
25	Execution timed out	3044 ms	2948 KB	Time limit exceeded
26	Execution timed out	3041 ms	3036 KB	Time limit exceeded
27	Execution timed out	3048 ms	2860 KB	Time limit exceeded
28	Execution timed out	3049 ms	2952 KB	Time limit exceeded
29	Execution timed out	3041 ms	2964 KB	Time limit exceeded
30	Partially correct	56 ms	2940 KB	Partially correct
31	Partially correct	4 ms	2392 KB	Partially correct
32	Partially correct	5 ms	2392 KB	Partially correct

답안 #916056

Compilation message

Subtask #1 0 / 30.0

Subtask #2 0 / 70.0

Subtask #1
0 / 30.0

Subtask #2
0 / 70.0