Submission #710553

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
710553	2023-03-15T10:58:04 Z	baojiaopisu	Gap (APIO16_gap)	C++14	100 / 100	81 ms	6944 KB

gap

#include "gap.h"
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;

#define fi first
#define se second
#define left BAO
#define right ANH
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz

#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

const int MOD = 1e9 + 7; //998244353

template<class X, class Y>
	void add(X &x, const Y &y) {
		x = (x + y);
		if(x >= MOD) x -= MOD;
	}

template<class X, class Y> 
	void sub(X &x, const Y &y) {
		x = (x - y);
		if(x < 0) x += MOD;
	}

/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/

const ll INF = 1e18;
const int N = 1e5 + 10;

ll findGap(int t, int n) {
	if(t == 1) {
		ll a, b;
		set<ll> num;
		MinMax(0, INF, &a, &b);
		num.ins(a); num.ins(b);
		int cnt = 2;
		while(cnt < n) {
			ll s, t;
			MinMax(a + 1, b - 1, &s, &t);
			num.ins(s);
			num.ins(t);
			cnt += 2;
			a = s;
			b = t;
		}

		vector<ll> c;
		for(auto x : num) c.pb(x);
		ll ans = 0;
		for(int i = 0; i + 1 < c.size(); i++) {
			maximize(ans, c[i + 1] - c[i]);
		}

		return ans;
	}

	ll a, b;
	MinMax(0, INF, &a, &b);
	ll d = (b - a - 1) / (n - 1);
	ll c = (b - a - 1) % n;
	ll l = a + 1;
	ll ans = 0, last = a;
	for(int i = 1; i < n; i++) {
		ll r = l + d + (i <= c) - 1;
		ll s, t;
		MinMax(l, r, &s, &t);
		if(s == -1) {
			l = r + 1;
			continue;
		}
		maximize(ans, s - last);
		last = t;
		l = r + 1;
	}

	maximize(ans, b - last);
	return ans;
};

Compilation message

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:86:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i = 0; i + 1 < c.size(); i++) {
      |                  ~~~~~~^~~~~~~~~~

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	0 ms	208 KB	Output is correct
4	Correct	0 ms	208 KB	Output is correct
5	Correct	1 ms	208 KB	Output is correct
6	Correct	1 ms	208 KB	Output is correct
7	Correct	0 ms	208 KB	Output is correct
8	Correct	0 ms	208 KB	Output is correct
9	Correct	0 ms	208 KB	Output is correct
10	Correct	1 ms	220 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	2 ms	336 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Correct	14 ms	2008 KB	Output is correct
17	Correct	14 ms	1964 KB	Output is correct
18	Correct	14 ms	2008 KB	Output is correct
19	Correct	18 ms	1996 KB	Output is correct
20	Correct	11 ms	2000 KB	Output is correct
21	Correct	81 ms	6944 KB	Output is correct
22	Correct	68 ms	6924 KB	Output is correct
23	Correct	57 ms	6868 KB	Output is correct
24	Correct	66 ms	6832 KB	Output is correct
25	Correct	52 ms	6844 KB	Output is correct
26	Correct	62 ms	6840 KB	Output is correct
27	Correct	59 ms	6844 KB	Output is correct
28	Correct	77 ms	6904 KB	Output is correct
29	Correct	66 ms	6828 KB	Output is correct
30	Correct	64 ms	6848 KB	Output is correct
31	Correct	1 ms	208 KB	Output is correct
32	Correct	0 ms	208 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	1 ms	208 KB	Output is correct
4	Correct	0 ms	208 KB	Output is correct
5	Correct	0 ms	208 KB	Output is correct
6	Correct	0 ms	208 KB	Output is correct
7	Correct	0 ms	208 KB	Output is correct
8	Correct	1 ms	208 KB	Output is correct
9	Correct	1 ms	208 KB	Output is correct
10	Correct	0 ms	208 KB	Output is correct
11	Correct	1 ms	208 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	208 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Correct	13 ms	512 KB	Output is correct
17	Correct	12 ms	500 KB	Output is correct
18	Correct	17 ms	464 KB	Output is correct
19	Correct	12 ms	464 KB	Output is correct
20	Correct	11 ms	516 KB	Output is correct
21	Correct	52 ms	1056 KB	Output is correct
22	Correct	63 ms	1084 KB	Output is correct
23	Correct	51 ms	1080 KB	Output is correct
24	Correct	54 ms	1080 KB	Output is correct
25	Correct	56 ms	1064 KB	Output is correct
26	Correct	59 ms	1068 KB	Output is correct
27	Correct	57 ms	1112 KB	Output is correct
28	Correct	63 ms	1084 KB	Output is correct
29	Correct	67 ms	1056 KB	Output is correct
30	Correct	30 ms	1088 KB	Output is correct
31	Correct	0 ms	208 KB	Output is correct
32	Correct	1 ms	208 KB	Output is correct