oj.uz

답안 #144670

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
144670 2019-08-17T11:02:57 Z cheetose Gap (APIO16_gap) C++11
100 / 100
 79 ms 3920 KB 
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 9876543219876543
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int,int,int,int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const ll MOD = 1000000007;
ll POW(ll a, ll b, ll MMM = MOD) {ll ret=1; for(;b;b>>=1,a=(a*a)%MMM)if(b&1)ret=(ret*a)% MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };

#include "gap.h"
const ll inf=1e18;
ll a[100001];
ll findGap(int T,int N)
{
	if(T==1)
	{
		MinMax(1,inf,&a[0],&a[N-1]);
		int i=1,j=N-2;
		while(i<=j)
		{
			MinMax(a[i-1]+1,a[j+1]-1,&a[i],&a[j]);
			i++,j--;
		}
		ll ans=-1;
		fup(i,1,N-1,1)ans=max(ans,a[i]-a[i-1]);
		return ans;
	}
	else
	{
		ll t1,t2,r1,r2;
		MinMax(1,inf,&t1,&t2);
		ll t=(t2-t1)/(N-1);
		Vll v;
		v.pb(t1);v.pb(t2);
		if(N==2)return t;
		ll ans=t;
		fup(i,0,N-2,1)
		{
			MinMax(t1+t*i+i,t1+t*(i+1)+i,&r1,&r2);
			if(r1!=-1)
			{
				v.pb(r1);v.pb(r2);
			}
		}
		sort(ALL(v));
		fup(i,1,(int)v.size()-1,1)ans=max(ans,v[i]-v[i-1]);
		return ans;
	}
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 380 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 15 ms 740 KB Output is correct
17 Correct 15 ms 732 KB Output is correct
18 Correct 15 ms 760 KB Output is correct
19 Correct 15 ms 664 KB Output is correct
20 Correct 11 ms 888 KB Output is correct
21 Correct 54 ms 1912 KB Output is correct
22 Correct 56 ms 2544 KB Output is correct
23 Correct 55 ms 2040 KB Output is correct
24 Correct 56 ms 2040 KB Output is correct
25 Correct 46 ms 2668 KB Output is correct
26 Correct 54 ms 1912 KB Output is correct
27 Correct 54 ms 2680 KB Output is correct
28 Correct 55 ms 2564 KB Output is correct
29 Correct 55 ms 2552 KB Output is correct
30 Correct 40 ms 1884 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 1 ms 348 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 20 ms 1432 KB Output is correct
17 Correct 21 ms 1524 KB Output is correct
18 Correct 20 ms 1400 KB Output is correct
19 Correct 20 ms 1400 KB Output is correct
20 Correct 10 ms 760 KB Output is correct
21 Correct 77 ms 3048 KB Output is correct
22 Correct 77 ms 2980 KB Output is correct
23 Correct 77 ms 2900 KB Output is correct
24 Correct 77 ms 2932 KB Output is correct
25 Correct 74 ms 3920 KB Output is correct
26 Correct 78 ms 3056 KB Output is correct
27 Correct 79 ms 2928 KB Output is correct
28 Correct 77 ms 2980 KB Output is correct
29 Correct 78 ms 3068 KB Output is correct
30 Correct 39 ms 2172 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct